Parece que usted está buscando una solución de verificación de direcciones "en vivo", en contraposición a una solución de procesamiento por lotes o "lavado".
En cuanto a los servicios de verificación de direcciones "en vivo", tiene razón en que USPS (Servicio Postal de los EE. UU.) Requiere que use sus servicios de entrega si usa su API. UPS (United Parcel Service) es de la misma manera. Aquí hay una cita de sus TOS (Términos del Servicio)
"Los Sistemas UPS y la Información deben ser utilizados únicamente por el Usuario de Acceso en relación con los envíos ofrecidos por, o para el Usuario de Acceso a UPS para la entrega y para ningún otro propósito."
Existen bastantes proveedores de servicios diferentes que licencian los datos de USPS y luego le permiten usarlos SIN cumplir los requisitos establecidos. La API de USPS es muy compleja y, a menos que la vaya a utilizar MUCHO, puede que no valga la pena la inversión para que se resuelva.
Con el interés de la divulgación completa, soy el fundador de SmartyStreets, tenemos un address verification API llamado LiveAddress.