However, law enforcement seems to think that now that companies are collecting all this data, they should have access to it, too, without restriction. The problem is that once these sorts of programs become common knowledge, the companies start being viewed as just an arm of law enforcement. Do you trust the local police? FBI? NSA?
No? Then don't trust these companies.
The solution to this is not to stop the mail tracking (tracking numbers are an awesome feature), but to curtail the reach and powers of the executive. Law enforcement shouldn't be able to request whatever they want from these company datasets.
So how do you fix it?
First, the business records laws on which these data requests rely are incredibly antiquated and not meant for huge networks of communications. So a solution is to update these laws to better protect user tracking data when it is in the hands of a company. However, Congress doesn't seem to want to do anything, so the legislative branch is losing power more and more.
Second, the judicial branch could step in and rule that these searches are protected under the Fourth Amendment. However, the executive has been claiming privileged on most of these cases, which means they get dragged on for years and years. Kudos to the EFF and ACLU for sticking it out, but the judicial branch is simply not keeping up with executive power grabs.
Third, users of the companies can start fuzzing or encrypting their data. In this article, a solution could be for someone to offer an aggregated address to which people can send letters. It's basically a manual VPN or onion-routing technique. Unfortunately, this tactic is very difficult to hide all metadata, so I'd prefer the first two options over asking users to fuzz their data.
Disclosure: I volunteer for Restore the Fourth, which is a 501(c)(4) organization advocating for greater barriers to warrantless or broad surveillance. We are currently focusing on getting local cities to pass privacy policies that limit what data local law enforcement can gather and share.
EDIT: I realize that the USPS is a part of the government, but it is not an arm of law enforcement. It should still require a warrant to obtain user tracking data from the USPS just like any other business.