Sort of an aside but I have only lived at one location that had home delivery, I have to pay for my PO Box currently but have had free ones in the past. Now that is a subject.
I have had mainly to go through Contract Offices and the amount the USPS pay those operators is very small. Someone I know bought a property that was a Contract Office and declined to take the Contract on, a guaranteed loser. The other problem is that USPS Employees, Contract or Direct are supposed to go through background checks. I think Direct employees also Drug tests which I joke would exclude the majority where I am. I know they have major staffing issues.
I have never had problems with USCIS, they ask for both as has been mentioned, COSTCO yes, they ship UPS but usually handed over to USPS for the last bit. And COSTCO system will chuck out PO Boxes. Usually I can mention the POBOX1234 whatever in the address so the system does not pick it up but the USPS employee does.
The only other way is to track it and get to the USPS office before about 10.30 on the day of delivery before they send it back.