I know this is an old thread, but I thought this might help.
There's a link to complain about missing packages, when you want to complain to the Postmaster General. They treat those search requests with priority. Because they're trying to divert your complaint from the Postmaster to a priority search request. They treat it sort of like complaining to Jeff Bezos instead of to Amazon Customer Service. Do not use the standard search request. You won't even get an automated reply for about 4 or 5 weeks, which is too late. You have to use that priority search request that's linked on the contact Postmaster General page.
When you submit your priority request, you'll receive a reply (appears personal with a name attached) and personal follow up on the search results. In your case, the search request will only work, if your package wasn't misdelivered or stolen off your door step. Because obviously, your package is gone and they can't get it back. But in most cases, (in my case maybe 100%) it's postal employees stealing packages. They pull the promising looking packages (jewelry, electronics) out of the system (tracking stops) and hold them for about a week. If no one comes looking for it, they steal it. So you have to act quickly. They'll know, if your package was delivered, because those electronic boxes used to scan packages as delivered record the GPS coordinates of the location of the delivery scan. So when you complain, they'll know if the package was stolen off your door step (GPS coordinates match your address), misdelivered (GPS doesn't match) or went missing inside a postal facility (tracking stops or scanned as delivered inside a postal facility).
Watch the tracking info closely. If the tracking stops, it most likely means postal employees have pulled your package out of the system, and are waiting to see, if anyone comes looking for the package. Or, if the package is marked delivered, does the tracking info make any sense? In few of my cases, postal employees scanned the packages as delivered inside the distribution centers and not on my doorstep. And the tracking info didn't make any sense. Because those distribution centers didn't deliver to my area. The tracking info should have said, departing XX distribution center, arriving XX local post office, sorting complete, out for delivery. But the fake tracking info said, arriving XX distribution center, delivered. The postal inspectors knew this, because the GPS locations where the packages were scanned as delivered had to have been inside the distribution centers. And I spoke to the mail carrier and he said if the tracking didn't say, sorting complete and out for delivery, it's not on his truck for delivery.
I hate to say this, but I suspect all of my missing packages except those from China (where they never shipped but were marked as shipped) were stolen inside postal facilities. I've had loads of packages (insured, Priority Mail) going missing in postal facilities across the country. I've never had that rare case where a package went missing for weeks but then unexpectedly showed up. Unfortunately, I'd say until someone does something about this, it's only going to get worse.
Sorry this happened to you. I hope this can help :)