the problem is a bug in the indexing algorithm. The reason is that PHP and MySQL handles accented characters differently. This is a known bug and it is very soon fixed. It will be fixed for 3.5.
The site is running with 3.4. and I don't think I'll update it as soon as the 3.5 will be release. This words "Déchetterie" (it's not a joke :) is important for my client because it's a service for inhabitants of a district (dump yard).
it is possible to patch this to into 3.4. I think it is some more work since there is a new library to handle string normalization. Look into the ezsearchengine plugin found under kernel/search. If you need it we can also make this patch via support.