I liked Bill Gates' idea of making senders pay a fee (perhaps a minimum amount specified by the recipient) and giving recipients the option of refunding it for personal contacts.
I used to work for a company that was the USPS's #1 or #2 customer (depending on the year). We spent a TON of money on spam. The biggest cost was the stamp.
If people have to start paying for emails- it will eliminate a lot of the spam -but it won't eliminate all of the spam- and companies like the one I used to work for will start to shine.
However, if they also had to pay me I would mind the spam a lot less.
The idea being that each email would do a non-trivial amount of work, such compute a valid hash - encode it in the message header. This message header can be checked quickly on receivers side, but takes time for the sender.
This makes sending a large amount of email quickly infeasible without a significant amount of compute power.