USPS lost a package of mine about a month ago. The clerk gave me the postmaster's phone number as she was not in at the moment. The post mistress was most helpful, and asked for a phone number she would call, if the search turned up nothing. It took 3 weeks, but I did get my package, which was lost within the P.O.
Of course this was a straight USPS shipment, no UPS/FEDEX. But I'd say to talk to the postmaster of your local P.O. Take it above the counter clerks.
