This is going to take some programming, of course. And it might not be worth it.
Also, think about this...
You know how you ask people twice to enter say, their password? People get it wrong. It's a good check to ask for this backup.
Even if you're not mailing them anything, but building a db, it's a good check to enhance the info's accuracy.
Now, if you are going to be mailing people stuff, you need to check out the USPS database where they'll make labels for you and such. A better investment would be to create an interface with their program.
Drill down deep into the postal service's web site for businesses that mail. And, of course, check out the other shippers web sites as well.
USPS does offer their raw database on CD at a cost. I think $1,000 a year, but I'm not sure about that. You'd need to be able to convert it to SQL or something, and if you're good with databases it's fun and powerful to work with. It will let you convert zip codes to cities and vice-versa, and validate complete addresses down to the apartment number and Zip+4.
zip codes used to be a service mark. they are not "public domain", they are an identification of a private corporation and are OPTIONAL in the united states: see Domestic Mail Services Regulations, Section 122.32. They should only apply to the places that fall under the jurisdiction of the District of Columbia.
As far as my limited knowledge of the subject goes, US has 2 separate laws, and 2 separate jurisdictions - State and Federal. There are people who fall under one and not under the other. People who do not fall under the "Federal" commercial law, will use addresses without a zip code.
A Postal Service is "quasi-government" agency, i.e. a private corporation, just like Federal Reserve. Zip Code™ does not apply to addresses that fall under the jurisdiction of a State only - as in 50 states of the union, excluding District Columbia, Puerto Rico, Guam and a couple of other territories.
Just my 2 cents, but when I abandon a cart, it is not because I have to type in my state and city. It is usually because I have cold feet about spending the money, or I discover shipping costs are too high, or I decide to shop around for a better price.
I applaud you efforts to make the process more seamless, but I think you should also examine some other areas if you are having cart abandonment issues.