There are address verification bundles out there. Not sure if you/your company is dead set on doing this programatically, but if they're willing to spend a little money, it can alleviate this headache.