Scandinavian characters in the query does not work as expected

Hi..

I have an issue in the Nominatim search (want to replace Google auto complete), but for some reason it cannot handle æøå unless its fully written.
Example: /search.php?q=Harald Hår gives and ok with no result. If i do /search.php?q=Harald Hårfagres it gives no result, but /search.php?q=Harald Hårfagres vei does give a response.

This does not seem right to me, and other locations that does not contain this characters works like expected from a Autocomplete standpoint.

Am i doing something wrong?