Every customer I've worked with insisted on having all addresses ran through the USPS verification API so they could get their bulk mailing discounts.
Even if you get the delivery/cost side under control, you still have to make sure you are talking about the right address from a logical perspective. Mailing, physical, seasonal, etc. address types add a whole extra dimension of fun.