They even tried just for the US, and not international, and it still wasn't good enough. It just changes too much and any inconvenience to the customer was not acceptable.
If you put in a city on the list, then you get the green SUCCESS (and probably some autocomplete suggestions to take you there), if you put in one that's not on the list, you get an no cue at all (or an equivocal one)
Then as you make successful orders to previously unknown cities, you can add them to the known list (possibly as aliases of the "real" city name, which you can then display as a choice to future users on entry.
Populating the auto-complete list with the 100 biggest cities and accepting any input would probably give a better compromise.
Or why not just ask for zip code first and auto-populate the rest?
Q: How often do the ZIP / postal codes really change?
A: U.S. ZIP Codes change sporadically. Most of the time there's just a few changes, but every now and then (especially around July 1st) there will be major changes.
----
... In other words, they change all the bloody time.