That is strange given that neither one relies upon the USPS database to verify addresses. You can go on the UPS website and validate your address yourself.
When USPS made the cost decision to not deliver, then UPS and FedEx quickly followed. I have most of my mail delivered to a free PO Box, all of my packages get delivered to my free mail box at the local UPS store. The number of houses impacted is approximately 800 maximum. In short it is a pain in the rear end and my wife and I would love to pay extra to get mail delivered.
The other unintended side effect of USPS removal of the address from their delivery list is as follows. For many financial institutions they require entry of the street address even if mailing to a PO Box. When they look up my address they use the USPS database and always reject all of my applications for having an invalid address.