Should be titled "Put the Zipcode and country first".

Would be simple enough to have someone type the zip or postal code first, then move the countries that are known to have that zip code to the top of the drop down (still in alphabetical order), and all the other countries below that (also in alphabetical order).

Leave all the fields editable, i.e. the postal code only suggests, ranks, or prepopulates.

Seems like that would handle all the edge cases, including those where a zip code doesn't refer to one and only one city, or where a zip code has changed or been added to a country.