You have a couple options. You can buy a bulk zip-code library from somebody which will list zip codes, cities, counties, etc. by state, or you can pay someone to access a web service which will perform the same function on a more granular level.
Your best bet would be to go with the zip-code library option, as it'll cost you less than the web service and will provide better performance. How you query or pre-process this library is up to you. You mention SQL Server, so you'd probably want State, Zipcode, and City tables, and include the relevant relationships between them. You'll also need to have provisions for cities that span multiple zipcodes, or for zipcodes that have multiple cities - but none of these issues are insurmountable.
As far as dealing with the vagarities of user input, you may consider enlisting the help of an address validation web service, although most of them require a full shipping address in order to validate.
Edit: looks like there's a SourceForge project offering free zip-code data, including lat/lon data, etc. Not sure how correct or current it is.
Edit 2: After some cursory looking on that SourceForge project's site it looks like this is a dead project. If you use this data, you'll need to provide some allowance for zipcodes / cities that don't exist in your database. Purchased bulk libraries usually come with some sort of guarantee of updates, or a pricing plan for updates, etc., and are probably more reliable.