If you can list the street address of the Post Office along with the P.O. Box number the USPS will accept it.
The reason FedEx, UPS, DHL, TNT, etc "don't deliver" to P.O. Boxes is that they don't maintain the same database of "which post office has which P.O. Box for which zip code" that the USPS does. If they don't maintain this mapping, how is the delivery driver supposed to know where to go?
EDIT: but the owners of the pizza place next door know me pretty well, and they have received packages for me before