При помощи анализа кода и обращений к внешним скриптам, был найден протокол получения данных.

Адрес обращения Яндекса для вывода подсказок при поиске региона:

suggest-maps.yandex.ru/suggest-geo
?search_type=tune
&v=9
&results=20
&lang=ru_RU
&callback=jQuery
&part=%D0%9A%D1%80%D0%B0%D1%81%D0%BD%D1%8B%D0%B9+
&ll=40.05799%2C47.894709

Разобравшись в переменных, стало понятно что:

v - Это версия формата вывода данных в JSON. На текущий момент их 9.
results - Количество ответов в выдачи. Максимум можно получить 20 значений
lang - Язык ответа.
callback - Формат вывода данных.
part - сам запрос. Первые буквы названия региона.
ll - Координаты, откуда идет запрос. Ответ данных зависит от региона запроса.

В результате выдаются данные в формате JSON, которые содержат название региона и искомый ID (geoid).

Осталось получить список всех регионов. Это усложняется тем, что Яндекс за раз выдает только по 20 регионов.

Соответственно, я решил перебрать всевозможные комбинации букв и цифр, и по каждой комбинации собрать данные подсказки и сохранить все в базу данных.

а б в г д е ж з и й к л м н о п р с т у ф х ц ч ш щ ъ ы ь э ю я a b c d e f g h i j k l m n o p q r s t u v w x y z 0 1 2 3 4 5 6 7 8 9

Множественным перебором данных получаются следующие комбинации:
a
aa
aaa
aaб
aaв
и так далее...

Все эти комбинации отправляются в Яндекс и собираются полученные данные.
Таким образом можно получить все необходимые регионы и Яндекса.

Что и было сделано! :)