well its not a partial fix thats a new thing your talking about.
Remember how your database saves it can be different depending on encoding etc
If your not finding it on a search of the string its because your database saves it some other way than your tryping it.
My database tables are UTF8 and when I store an umlate it is stored correct like example
That is stored in my database as that and is very searchable.
Now what I would suggest is searching for other matches or partial matches to find a string.
Again category editing is something different than what we have been discussing on language editor.
Any announcement box in the adm-cats.php script I would need to check for any htmlspecialchars line and try commenting that out.