Dan,
I investigated the sample files. Thanks for providing them. The Sébastien text can be found with Find, but you must copy the exact text from the Caption field of your photo. If you enter Sébastien by typing:
S, Option-e, e, bastien
...it won't work. The data in XMP is not entered in the same way. Let me explain-- if I look at the data that makes up the characters in the Caption field and the characters you likely typed I see:
Caption: Se(0xcc 0x81)bastien
Find: S(0xc3 0xa9)bastien
The Caption version is: S, e + Combining Acute Accent, bastien
The Find version is: S, Latin Small E with Acute character, bastien
The find / replace functionality looks for strings of bytes that match. It is fairly simplistic and cannot handle the case you've provided. It would need to be upgraded to a fully Unicode-aware search that would normalize the data to be searched and the search string itself.
Regards,
-Kirk