99,999 Innocent Bystanders Spammed

First some depressing statistics, then some interesting proposed solutions, all based on increasing the cost of spamming: 99,999 Innocent Bystanders Spammed by Microsoft Research.

I like the solution that requires the sending computer to do some kind of computational analysis in order for a receiving computer to accept a suspicious message. Not sure how that would be implemented across all platforms though.