Encrypting email to a single recipient is (a weak) proof of work.
There's a big difference between sending 10k copies of a plaintext email, and retrieving a public key and encrypting to 10k recipients - not to mention that filtering out all non signed/not-signed-by-trusted-key should be a decent start for a whitelist/greylist.
I'd be curious if anyone ever got gpg-encrypted spam?