I've been researching alternatives and Mapfit offers 100,000 API requests a day for free. I haven't read the documentation but looks very promising.
Well a truly bizarre thing happened, the Mapfit staff just altered the text on their pricing box from 100,000/day to 2,500/day (Google cache confirms). Doesn't look very professional.
They’ve probably been getting hammered with signups. It sucks they pulled such an underhand move but it’s obvious why they did it.
Usage: 10000 requests / day
Google Maps: (3600000 - (28000free * 12)) / 1000 * 7 = 22848 $ per year
Yandex Maps: 360000 rubles or 5600$ per year, but much cheaper for higher volumes than 10000/day
Mapbox: (3600000 - (50000free * 12)) / 1000 * 0.5 + (fix 500 * 12) = 7500 $ per year
Bing Maps: No pricing on website, need to contact support