US Addresses

I've been looking into using a street address database... so that users of my program can be sure that a customer's address is valid when they input it for a sale.

I know USPS has some sort of WebTools API that allows this, and it would be a great solution since it uses XML to access their database, relieving the program of any need to access a database locally. This of course has some slight restrictions, namely, it requires a constant connection to the internet. Not too much of a problem in a store that is hard-wired to the net. But also, it requires a username and password for each copy of the software (although this is currently under review at USPS)

Then, I have seen some US Addresses databases on CD's, ranging from 3mb - 450mb ($50-$180). These are great, because one, I can extract the data I need (99% of our business is with customers in-state), and restore it in a filtered database (ie.. just the addresses for the state of Wisconsin). There are drawbacks to this as well, one being the addresses should be updated at least once every two years if not more.. which would require purchase of an update.. which is ridiculous since they are just pulling the info from USPS and throwing it into a database.

Really, all I want for this solution to accomplish is to rectify mailing addresses with the proper Postal address so that:

Jim Beer
113 East Washington Avenue Apt 5
Milwaukee WI

can become:
Jim Beer
113 E Washington Ave #5
Milwaukee WI 53202-1232

and even change:
Jim Beer
113 E Washringon Av 5
Milwaukee WI

into:
Jim Beer
113 E Washington Ave #5
Milwaukee WI 53202-1232

Anyone with comments or suggestions?