My solution is the following:
Replace the umlauts from the input with our private encoding for them, that is <UL>o</UL> (we have no umlauts on our keyboards, although we are in germany!) and replace them back to ö in the output.
Konqueror still gets the internal server error (that i send back via a "die") when it sends the two letter encoding. Opera encodes it as F6, and it works. With Mozilla i cannot enter an ö, and if i change the request line i get int the case of %F6 the wanted matches and in the other case the internal server error.