If you look further down the link that @Jackmannii shared you will see that the “Articles bearing political or religious notations on the address side” restriction is only for USPS, not UPS or FedEx. I’m sure the OP’s problem is a USPS worker mis-interpreting their internal rule.
Here is an old thread in a similar vein (TL;DR - the USPS prohibition against loose playing cards is based on obsolete German law which expired in 1981):