I did a test with different Geocoders (Google, MapQuest, Bing, Yahoo, Nokia). Google was lightyears ahead of the rest in my test. It was for the Netherlands, though.
The netherlands is a different beast when it comes to Geocoding since each postcode only corresponds with around 10 buildings all very close to each other. Most other systems cover larger delivery areas. My complete amateur comment is that you need different algorithms for different countries.