That same thing has happened to me once, but not with the postal service- it was with an airline. I had four proven pairs of Sun Conures shipped. Now, when you ship birds by air, they arrive the same day and you go pick them up at the airport.
The seller shipped them and they didn't arrive "supposedly" on the plane. Long story short- four days and about a hundred phone calls to various people later, they found them. When we went to pick them up, all of the males were gone out of the crate (which was sealed shut). All of the females appeared to be in perfect health despite "supposedly" not having food or water for several days in the middle of the summer.
To this day, I am convinced that one of the airline employees had them all along (hence they didn't appear hungry or thirsty) and finally turned some of them over probably because someone or multiple knew they had taken them. I filed a claim with the airline and eventually was awarded $2,500, but they treated *ME* like I was a criminal through the whole process.
I am sure those chicks are safe in some postal worker's back yard as we speak.