Is this because there is a conversion from "Ø" to "O" in the query? The letters "Æ" and "Å" gives similar results. "Åbe" (for Åbenrå) returns Abeokuta first.
the behavior of the name_startsWith search service has been changed to overcome the issues pointed out in this thread.
The service now does a sorting with a certain name similarity of the top 200 rows.
If you are particularly interested in a country we also suggest to use the countryBias parameter to list the hits for this country on top.