If I had the time I'd start something I'd call the "signed mail initiative" -- participants send only PGP signed mail, and prefer (in mail filters etc.) to receive signed mail. They'd use a standard sig line letting people know this policy, and directing them to information on how to "join" the initiative, guidelines for corporate and ISP participation, etc.

Regardless of whether the signatures are in the strong set, are trusted, or even known, this will help to both detect and reduce SPAM: the act of signing is itself compute-intensive enough to act as a small postage charge; each unique message will have to be signed; SPAMers will want to send fewer unique messages; this will help collaborative filters detect SPAM again; eventually any unsigned mail will become suspect in the first place.

As both participants and SPAMmers become more sophisticated, participants and their MUAs can prefer longer key-lengths, better signature chains, etc. This promises a wonderful arms-race of hardware and crypto escalations, but at least that will be better than the indefensible position which mail users are in right now.

That *might* work .. but you might be surprised at the results - spammers are intelligent and they can do things like harness 1000's of stolen machines for creating signed messages.

If you were to do that, I'd suggest you pick an algorithm that was very easy to check, as you will want your filter to dispose of falsely signed emails. One way to do this is to simply put a work factor in your email sig; something like "I want signed mail where the first 8 bits of the hash are 0" ...