I confess ignorance on the particular details of whether a PGP-encrypted message leaks who the sender/receiver are, though supposing it does it only leaks a single token--a username-email pair. If the state can read everything you as an individual send, they can only know who you're communicating with if the PGP-encrypted message itself leaks a name that maps to another offline individual. You could argue that a PGP-encrypted email leaks the name by default--i.e., the recipient of the email. You tell me how useful it is to know that I sent a message to cornflakesrule12345@emailprovider.ext without knowing what the message says. (More information can of course be found by coercing the particular email provider, if you can, to give up an IP address of the user, but we all know how reliable IP addresses are at pinpointing a single offline individual and there are many other options...)

Of course, we can go further down the rabbit hole of schemes, we don't have to stick with just PGP. As one of your sibling-comments noticed, anyone who wants to get around any State Spying can do so as long as the State leaves room for some reasonable assumptions. (As for outlawing encryption, that's a problem on its own, both in enforcement and in definition. You'd likely just get particular encryption software outlawed rather than the concept. (I'm aware of the US classifying certain algorithms as munitions.) Funnily enough, telegraph operators tried to outlaw simple ciphers and encodings (like 'u' for 'you' and even anagrams) used back in the day because they were losing money, since they charged a fee for a message length.)

I like the '89 paper entitled The Dining Cryptographers in the Disco: Unconditional Sender and Recipient Untraceability with Computationally Secure Serviceability. Here's part of the abstract:

We present a protocol which guarantees unconditional untraceability, the original goal of the DC-net, on the inseparability assumption (i.e. the attacker must be unable to prevent honest participants from communicating, which is considerably less than reliable broadcast), and computationally secure serviceability: Computationally restricted disrupters can be identified and removed from the DC-net.

> I confess ignorance on the particular details of whether a PGP-encrypted message leaks who the sender/receiver are

An important part of public key cryptography is the "web of trust" - you must know that you're sending stuff to the right person. A person's identity is tied to their PGP key.

> You tell me how useful it is to know that I sent a message to cornflakesrule12345@emailprovider.ext without knowing what the message says.

They build up big databases and then mine that for information. Most people are not disciplined enough to use cryptographic technology properly; and that holds for "not doing stuff that leaks data". Associating username@example.com with a set of data is an important step in getting the identities of both username and the people username is communicating with. Don't forget that even if username is careful the people that username emails might be idiots.

Both good points. From what I've been reading, "pattern finding" databases instead of "hash finding" databases are starting to be the new thing that allows huge and useful data analysis, and you can find patterns among a collection of lies or even just otherwise random data that wouldn't be associated without the pattern matching.

Fundamentally, it only takes one matching join on your citizen-data against any other collected assortment of data to implicate you. Human stupidity will continue being the weakest link. But there's still a lot that can be done to guard against it.

Even if the government manages to figure out that user@example is an Al-Qaeda member, and they know I sent them an email, they have no idea what I sent without resorting to, depending on how secure I was, torture, bargaining, private key compromises of the receiver, further insecure communications from the receiver's end, or hard drive sniffing for the original message from my computer. Increased carefulness can guarantee the message only exists within the minds of the sender/receiver, but with the advent of the "forgetting pill" even that vulnerability can be accounted for when plotting world domination. Of course as you note, human stupidity can undo it, but that's no reason to give up adding more layers of security.