How 'bout this:

Why not just have all mail servers setup with their own GPG keys, listed 
on some public GPG servers, (in a way like the root DNS servers, 
redundant and self propagating) and have them all sign the header 
portion of an email upon sending out.  When the receiving SMTP server 
downloads the email, it also downloads the GPG key from a keyserver if 
available (or use a cached one, much like cached DNS records, giving you 
the option to cache them or not, and a certain timeout period), to check 
the headers are actually from the sending server, unforged and 
unmodified?  If not, it rejects the email outright, and sends it to 
/dev/null...

Using GPG, trusted SMTP hosts can sign other known-for-sure-good SMTP 
hosts for the trust, just like the standard GPG/PGP way of doing things, 
based on the number of 'good' emails received from the host, preventing 
spam relays from being able to send email.  The number of other trusted 
smtp hosts that sign another's key increases the rating, so even if a 
spam relay gets signed (even a few times), it still won't rate high 
enough to not be considered spam, and dropped at the gateway.

If root GPG servers are unavailable, the email will be held in queue 
until the GPG servers are able to be checked positively if an SMTP host 
has a good key, or even a key at all.  Then, even if spammers DDOS'd the 
root GPG servers, instead of allowing a flood of spam to get through, 
none would get through, until the DDOS attack subsided, and the email 
servers were able to access the keyservers.

Mailing lists could require you to upload your public key to it's 
private stash upon subscription and compare it to your to-be-posted 
email to prevent email spoofing to post to the list...maybe that's a bit 
overboard...

There's probably some bugs in my thought, as it's late, and probably as 
many cons as pros - one being *everyone* would have to participate - 
otherwise we'd probably be using this type of spam protection right 
now...Just a thought...would be great if we could get all the MTA's to 
standardize on it and start using it.

Hell, if GPG/PGP were more popular and more people used the technology 
(especially on mailing lists, and online communities) I'm sure that 
would cut down spam quite a bit - and it'd be open and proably better 
than M$'s proposed 'paid email postage'...

-Lucas