Pedalkin спасибо за идею. Я много разных провайдеров посмотрел до этого, но про них как-то не подумал. У них довольно хороший бесплатный порог, выше чем у Яндекса (50 тысяч вместо 25 тысяч запросов в сутки). Хотя не сравнивал как они считают запросы, возможно там есть какая-то подстава. Но есть и свои приколы - программа может быть только под Windows, на Linux и Mac использовать бесплатно нельзя. Возможно есть и другие приколы, типа недоступности спутниковых снимков (они ведь тоже их покупают, а не сами делают) - но это надо будет уже детально изучать договор, я пока этого не делал.
В общем, пока у меня складывается ощущение, что в будущем придется сделать поддержку одновременно нескольких провайдеров, и в разных случах и на разных платформах показывать разных, чтобы и не нарушать их ограничения, и при этом максимум функциональности получить.