Eastern Europe (AMS) Topographic Maps (Series N501, U.S. Army Map Service, 1954): a series of 380 maps in a scale that should show almost all villages.
The US Board on Geographic Names site (USBGN)
Polish Gazetteer: Skorowidz miejscowosci Rzeczpospolitej Polski : (includes western parts of Ukraine, Belarus and Lithuania) http://www.wbc.poznan.pl/dlibra/docmetadata?id=12786&from=publication (Click British flag in right hand corner for English.)
Old maps of Poland and Central Europe: Mapy archiwalne Polski i Europy Środkowej (Click British flag in right hand corner for English.)
Geographic Dictionary of the Kingdom of Poland and Other Slavic Countries: (1893) Slownik geograficzny Królestwa Polskiego i innych krajów słowiańskich (includes western parts of Ukraine, Belarus and Lithuania)
The JewishGen Communities Database and JewishGen Gazetteer: (Shtel Seeker) based on the USBGN place names but has extra functionality such as soundex. Using a button, you can click on a particular place that will then give all the places within a 10 mile radius.
General Map of Central Europe: (3rd Military Mapping Survey of Austria-Hungary)
Genealogical Gazetteer of Galicia by Brian J. Lenius: (book)
Bukovina Gazetteer: Gemeindelexikon
List of Populated Places in Imperial Russia: Spiski Naselennykh Mest Rossiiskoi Imperii also on microfiche at the Family History Library
Maps search: Google Maps and for Cyrillic map search