Oh wow, responses about my gpg comment. Let me get replies in before it all leaves the recent log:
tmorgan: While I find the idea of somehow distinguishing between different levels of trust in the key infrastructure interesting, I think that would make it too complex for the non-technical user. Keeping it at "I trust this person not to send spam" is straightforward and has an obvious, big payoff for everyone involved (the spam problem is only getting worse).
I don't know to much about how it all works either, but I have read that some people have one key for signing and another (usually longer) key for encrypting. So perhaps one's signing key could be a spam trust key, and one's encrypting key could be a super-duper I rilly know you trust key. Mere mortals could be happy with the anti-spam key.
dyork: You're right, of course, about client support. I have been impressed enough with the usability of the Thunderbird/Enigmail combo to think that might be the app that will work for non-techies. (I've never tried gpg on Windows, though -- I'm just guessing things work similarly in that universe.) Home users have their choice of clients, and effective spamfighting might be enough of a draw to make people switch. Thunderbird is a typical GUI mail client; I think anyone could get used to it without much effort.
I know you don't have much choice about mail clients at work; I know that Outlook has a nice plug-in architecture which makes it seem like it might be possible to add a gpg plugin there. (I don't know much about it, but I installed the SpamBayes Outlook plugin at my work and that integrated seamlessly into the client.)
Critical mass is the key, and I can see a glimmer of hope that changing the definition of "trust" to make signed messages useful in blocking spam, combined with new, easier to use clients, could just make it all take off.
Everyone hates spam.