About six months ago, I posted asking how to cut down on the paper spam I get (most especially the smirking goateed realtors). Several people recommended GreenDimes, and I signed up. You give them your info and $15, and they periodically re-unsubscribe you from various lists. And they plant some trees.
It seems to have been working very well!
Pretty much the only spam that hasn't stopped is AT&T ("Your World Delivered. To the NSA.")