However, creating new publick/private key pairs is an incredibly
expensive operation, and one that a legitimate email wouldn't have to
do very often, but a spammer would if we just keep blacklisting their
keys.
Uh? Creating a Diffie-Hellman public/private key pair is actually quite
simple. Even an RSA pair is not all that hard, considering that a set of
N prime numbers can generate N.(N-1)/2 key pairs. The logical
consequence of authenticated e-mail is bound to be authenticated spam...
-- Christian Huitema