We are looking for a free or paid version of a Geocoding API that will allow us to use it for commercial purposes that is as good as google. Google's api starts at $10,000 a year which is too much. We expect to do 1000-5000 geocodes per month.

I have tried Cloudmade, but have had problems geocoding some addresses that google can do.

Does anyone have any recommendations based on experience?