It's a bigger mod, but I've also done something like this with the data from
www.zipcodedownload.com. You have to pay for the database, but with that info I'm able to verify their city / state match their zipcode. It saves a ton of money on reshipping packages and changing addresses en route.