Как лучше реализовать поиск по адресу?
Мне кажется проще использовать api yandex-а или других карт. При чем не только для этой конкретной задачи, но и  в целом для всего что связано с координатами, улицами и т.д. Сделал запрос, получил результат.
Кстати в ВКОНТАКТЕ гео инфа без токена получается. Там наверное проще будет.
vk.com/dev/database.getRegions
Через Google Maps API можно попробовать.