In Easter Europe even Google Maps are much worse that OpenStreetMaps.
I am working on a project where I have noticed the same problem with several providers. What provider do you recommend for geocoding when this stuff needs to be right most of the time? Bing API seems somewhat OK. Google Maps API seems like the best, but comes with insane terms and conditions.