We have options already, although we abandoned them once the Internet became ubiquitous. UUCP would allow encrypted envelopes that would only allow trusted nodes to decrypt enough to forward to the next destination or to the local user.
It would be ungainly, especially at first, and just as easy to scoop associations between users (although, not subject lines or other metadata) by tracing the limited paths. As a critical mass were achieved (yay network effects), along with peer-to-peer sharing, you could source route your messages to anyone.
Given this message:
From: reeses
To: hagbard
Subject: fnord
Please immanentize the eschaton at your earliest convenience.
I could route it through the equivalent of a bang path (foo!bar!baz!bob), each step of which is a trusted node whose private key(s) I have in my routing table. Instead of bang paths, however, the envelope could be something as simple as:
Next: baz
Data:
Ardhrcbeebdhvfdhnzrfgdhvqbyber
zvcfhz,pbafrpgrghe,nqvcvfpviryvg
baz would receive the "Ardhrcbeebdhvfdhnzrfgdhvqbyberzvcfhzdhvnqbybefvgnzrg,pbafrpgrghe,nqvcvfpviryvg" blob and unwrap it, forwarding it to bob, who would have exchanged keys with reeses.
Multipath routing and multiple recipient support would be possible by having additional Next: headers and the encrypted blob would serve as a sufficient identifier, or input into an identifier generator, to deduplicate messages if a transmission fork were coalesced.
This is off the top of my head, so it's wrong in a bunch of ways, but it's a simple model that could easily be deployed among circles of people who need a degree of anonymity. As in the later days of UUCP, with comp.mail.maps and the like mapping a combination of FQDNs to named hosts, initial, intermediate, or terminal nodes could involve forwarding over (E)SMTP. (foo!{bar|baz}|quux|reeses@example.com) would route through a number of machines, and the message in my inbox would look like the following:
From: POSTMASTER@quux.com
To: reeses@example.com
Subject: (none)
-----BEGIN PGP MESSAGE-----
Version: 2.6.2
PnyyzrVfuznry.Fbzrlrnefntb-arirezvaqubjybat
...
Again, at the beginning, it would just be necessary to know about quux (or just the message fingerprint) and monitor its traffic to identify reeses@example.com as
someone up to no good and watch for sidechannel communications to create a correlation between conversants. "Hmm, reeses received a message at 3:14pm from an unknown source. Ah, he received a phone call from 415-555-1212 at 2:58pm and called that number at 3:18pm." Multiple transmission sources, split messages (torrent file pointing to message, etc.), unconventional channels, and the like could wrap enough layers of encryption (and yes, STO) that the feasibility of a timely interception of content would be significantly reduced.
Plus, rubber hose.