Я такое делал. В "Гаранте" есть Отраслевой Классификатор Административных Территориальных Образований России (ОКАТО). Он содержит даже аулы и полустанки. Трехуровневая иерархическая классификация (весьма запутанная и подчиняющаяся разным правилам для разных регионов). Однако, вполне подходящая для решения подобных задач. Закачать в виде таблицы сможешь в момент. А вот чтобы превратить эту струтктуру в дерево, придется помучиться. Особенно, когда выяснится, что в классификаторе имеются опечатки (в самом коде!) и, как ни странно, повторяющиеся по нескольку раз участки (то есть, один регион с одним и тем же кодом может попасться более одного раза).