Currently there are 3 options that may help:
1. Use the search in All Map to find any town with population greater than 1000.
2. For smaller towns, try using the Nearby Search after zooming into the middle of the country and setting the Nearby Search Radius to 128km (may not work for very big countries obviously).
3. Use the Online Address Search, leaving the street field blank.
One of the improvements we intend to make in the next several months is to internationalize the All Maps data which will include having it show Nearby > Areas data for smaller towns in any country/region that has been downloaded.