Тоже была проблема с городами половцев, вот что у меня есть:

<City>TXT_KEY_CITY_NAME_SHARUKAN</City>
<City>TXT_KEY_CITY_NAME_SARKEL</City>
<City>TXT_KEY_CITY_NAME_SUDAK</City>
<City>TXT_KEY_CITY_NAME_AKKERMAN</City>
<City>TXT_KEY_CITY_NAME_MILKOV</City>

Города были взяты из каких исторических карт, с инета.