I need to find a piece of software with an API (application
programming interface) that will take an address and validate it and
return the validated address back to a calling program (written in
C#/VB.NET).  It's got to be able to interact programmatically (e.g. it
can't be a standalone application).

Some possible starting points might be the USPS web or Pitney-Bowes.

Pay goes to the person who identifies a viable product.

UPS does this over the web as an API.  I think you need an account
with them, however.

FirstLogic does exactly what you want.  It will run as a service on a
server and you interact with it via an API.  You pass an address and
it returns cleansed and possible address selections if the address is
off a bit.  I used it for a major website in 2001 and it worked great.

http://www.firstlogic.com/solutions/mailing/default.asp