Strange problem with Search widget and international characters

Hi people! I have encountered a strange issue with the Wordpress search widget. I have noticed that the first - but only the first - search you do with it using international characters - German umlauts in my case - fails because of an encoding problem.

For example, if you search for "Größe" with an ö in it, no search results are found because the search resolves in the address bar of the browser to:

/?s=GröÃ%C2%9Fe&submit.x=0&submit.y=0

If you then enter it again it resolves to

/?s=Größe&submit.x=0&submit.y=0

and the search works.

If you revisit later - presumably when your browser cache is cleared - the problem occurs again. Any ideas what this could be? It does not occur if I switch to the Wordpress twenty fourteen theme.