We have used Smartystreets in the past, one benefit of it is that you can script against their API to create an address validation for any data source. Also, Precisely (Pitney Bowes) has a bundle for address validation, and while the bundle itself only works on address records, they can provide access to a REST-based web service for validating custom addresses as well.
We are using Precisely’s bundle now, but for a totally custom, scripted solution, Smartystreets is probably the better option.