What happens when you try a different page encoding?
Modify > Page Properties > Title/Encoding
The menu writer should work on any of those, - I guess you just need to try different encodings until the search function works OK.
Non techie answer, but that would be my first step.
Edit: Sorry - Ignore mine - Jason beat me to it.