Hey, I don't know if it has been mentioned earlier (looked through the forum but didn't find any report on it - if I use the shortcut for google (default ctrl+g) it doesn't submit umlauts properly (öüä = öüä)
i think whatever you put in that search box has to already be in a form that works in a URL, since that's how it's submitted, so for instance, ü would have to be replaced with %FC etc...
I tried search engines like google, lycos, infoseek, altavista, excite and given a search word with national characters (like umlaut) and they all render the national language characters (NLS) correctly in the result text.
Indeed in the url box such a character is represented with %xx.
So I don't see too much of a problem.
There was one search site, mamma.com, which didn't render the NLS characters, but instead the kind of characters you describe.
I have nothing set specially in KM for NLS support, but as my Windows XP is a Dutch one, that may be the reason.