The best analogy re: address info on mail is to garbage that you leave on the curb for the trash collector. You probably don't have a reasonable expectation of privacy in that garbage because you exposed it to the public by leaving it out on the curb. There is case law to back this up. Similarly, if you hand over a letter to a postal carrier, you arguably wouldn't have a reasonable expectation of privacy in the info on the envelope since that info can be gleaned by anybody who looks at the letter. Email would be different since that is presumably store on your computer or a server or some other place or thing that would fall under the 4th Amendment protections (and require a warrant).

In a way email is worse, due to all the third-parties who might conceivably be "shown" the email en route.

Perhaps the courts will come up with a legal construct that information which is processed and handled in a completely automated fashion does not "count" as having been seen in public. Something similar to DMCA safe harbor and "common carrier" provisions already defined in telecommunications law, except that it would apply in general and not just to 'large enough' websites or telecom companies.