Give OpenStreetMap a try. It is free and open. Just they way these things ought to be. You can set up your own geocoding server with Nominatim: http://wiki.openstreetmap.org/wiki/Nominatim#Reverse_Geocodi...
There is a VM to play around as well: http://www.openstreetmap.org/user/AndrewBuck/diary/17698
Also there is Mapquest's API which uses this: http://open.mapquestapi.com/geocoding/