Maybe I'm alone here, but I never had an expectation of privacy in regards to what I write on the outside of a envelope and drop into a public receptacle (mailbox). I expect the contents to be considered highly private, but not the outside.

There's also this issue of willing disclosure of information to an entity. When I put a stamp on something and drop it in the mailbox, I know I'm handing that information over to a government authority (or whatever you want to call the USPS's weird relationship to the government). Regardless of what they are or aren't supposed to do with it, the fact is that I know I'm putting my info in their hands and trusting them. This is unlike PRISM, where I send an email through Gmail with no expectation that it should ever pass through government hands.

Also, I'm under the impression that most if not all hand-written addresses are digitized for sorting purposes. I think you have to be naive to assume the postal service wasn't keeping that data on file.