US Address Validation (Zip+4)

Possibly the easiest solution to use is the USPS's address API (http://www.usps.com/webtools/htm/Address-Information.htm#_Toc131231396) The usage regarding scrubbing databases is a bit vague (and if you ask them about it, it seems they remain just as vague, perhaps on purpose) but once you get approved it's VERY easy to send the data you have and get back a fully verified, 100% compliant and up-to-date address. Once you get the data back from USPS, you can simply add/subtract/agument it as you need prior to stuffing back into the DB. For instance, you could Geocode from the verified address, or from your DB, then append that data into the data you received, inserting in a loop.

I'm using it on one of my applications to validate inbound inquiries and it has proven nearly 100% reliable for getting me what I need corrected.

One thing to note about the USPS free API is that their license says the data it returns must be used only for sending things via the USPS. We had a need for ZIP+4 data but we ship our stuff through other carriers, so this meant we could not use the free service.