You could, in theory, run desktop software and plug into any kind of API it provides, but then you become responsible for things like uptime, data updates, and associated overhead. You may also run into issues with the software threading model--is it multi-threaded or single-threaded software? You don't want to find that out in production.
There are a handful of web services out there that can verify US-based addresses, including the USPS official web service. The USPS one is very limited in the fields that it returns. For example, if you're looking for the "delivery point" which is used to make a full barcode, the USPS API doesn't return that information. I believe the USPS web service also limits the number of queries that you can perform, although I don't remember the exact limit.
A few things that you'll want to look for in a web service include the price (obviously) as well as geo-distribution of their servers. If a company has all of their servers in one location and that data center goes offline (which can and does happen), you're left out in the cold. If they have multiple physical locations, it can help to prevent unnecessary outages. Also, you'll want to make sure that the service call returns all necessary fields as per your requirements--like delivery point code, barcode, and DPV code (which tells you how deliverable an address is).
Lastly, you'll want to determine how you feel about interacting with the company. When you call them on the phone, are they responsive and concerned about your needs? Or are you talking to some front-line person that can't answer questions and is only able to gather information about your company size and revenue so they can evaluate how big of a fish you are and determine which salesman gets to call you back. Can you talk to the engineers that wrote the web service on the phone or via email?
There are a few choices out there and you'll have to choose the one that best fits your requirements and unique situation. Do a Google search to find a list of companies. In the interest of full disclosure, I'm the co-founder of SmartyStreets. We have an address verification web service API called LiveAddress. You're more than welcome to contact me directly with questions on my personal Twitter account or the company Twitter account.