I've implemented it, too, and didn't run into any problems. User inputs the zip code, if there's multiple city matches, they select the correct one from the drop-down (or you auto-complete the city name after they type the first 4 letters).

The fact that "A city can also exist in multiple zip codes. And there can be multiple cities with the same name in the same state" is a good point IN FAVOR of asking for the zip code first (NOT to avoid it) because you certainly can't do it the other way round.

And if you just leave it to the user to free-type all that info in, you have to verify it after... Users are going to make typos, and the USPS will kick your butt if you don't correct it (and credit card payments won't go through, either). So it may be less work for web-form creators, but pushing the verification down stream just makes it all worse for the company using it.