A free market solution would be to offer more options. Automatic, universal encryption or digital signatures applied to everything genuine would be a legitimate solution to spam, and everything else gets dropped by your server.
And how exactly would encryption and signatures make sure the content is not spam? As long as email costs nothing but the electrons they'll continue to carpet bomb us with spam.
The solution must be some form of whitelisting, not blacklisting system. Mailing lists and outgoing mail addresses are trivial, the question is incoming mail from previously unknown sources. Personally I'd suggest doing a hash collision to burn CPU time, implemented like this:
1) Server auto-replies with a mail that says you aren't whitelisted, sending the requirements both as email headers (for automated calculation) and in the body as well as a link to a hash calculator.
Example using "user@fromdomain.com" to "user@todomain.com":
Hash-algorithm: SHA1
Hash-collision-strength: 25
Hash-base: user@fromdomain.com->user@todomain.com
2) You either
a) Go to a website that uses javascript to calculate the answer
b) Use a local application to calculate the answer
c) Have a email client that does this for you
c) Have a webmail provider who does this for you
Hash-solution: user@fromdomain.com->user@todomain.comA3BHG
Hash-value: 007afcd67d58c76d786c
3) Hash is verified to be a 25 bit crash with 00000000000000000000, message is delivered and sender is whitelisted.
Some nice things:
1) No protocols need to change, one server can start
2) The sender only needs a CPU to do the work
3) Difficulty is adjustable based on server/account settings.
4) It could eventually become entirely standard and automated.
5) The sender must exist and receive the response
6) You can do it even for non-existing email addresses
7) One base per sender/receiver pair, no easy way to cheat
8) The whitelisting is only valid for that sender, not all the spammer's friends
The obvious downsides:
1) Some people won't figure this out or won't do it, you might have to use a regular email if you absolutely can't afford to not miss any mail. However, the market for "semi-public" email addresses to use in forums and mailing lists should be huge to get it off the ground and eventually it should become something your email client does in the background.
2) Lots of unnecessary burned CPU time (but less than SPAM filters today? maybe not)