Yeah, USPS can be picky.
I have a repeat customer who I give a free upgrade to UPS every order because USPS won't accept their address, "US HWY 25E". There is no street number, and I can't find a different mailing address in the yellow pages, white pages, google, or anywhere. They are larger orders, so I don't mind spending the couple extra buck for it.