Kirk Allen Evans' Blog : Why Can't I Find a List of Zip Codes, Cities, and States?.
Kirk, who’s part of the team that I just joined @ Microsoft (that’s another story…) has a post on Zip Code lookup and interaction.
There’s a number of comments on how to get the data and a few good pointers:
The last one, looks quite cool and would be far more useful outside of just a zip code lookup – mapping particularly.
One that is missing, and yes, this is a direct competitor to Microsoft is the Google Maps API here http://www.google.com/apis/maps/documentation/