My team had to look at this earlier this year. We looked at and tried a number of solutions including those from Melissa Data, Qualified Address and Pitney Bowes, among others. All of the above services were CASS certified and could tell us if an address actually exists (DPV). We wouldn't even touch it if it's not CASS certified.

Management didn't want to spend $25,000-50,000/year on address verification, so we finally went with Qualified Address because their pricing blew everyone else away: http://www.qualifiedaddress.com/Services/Address-Verification-API/Pricing/

The other cool thing they had was a JavaScript version of their address verification. We put it on our checkout, which took about 10 minutes, and now our customers certify their own address (because ultimately they're the authority on their own address and where we ship the product). In this way we have quality data from beginning to end instead of trying to create quality from raw data. Our customer service department says we should have done this a long time ago - because the number of returned products because of incorrectly input address data is virtually zero.

We also looked at NCOA, the USPS charges $175,000/year for the data, so we'd definitely recommend a provider for that as well.