I'd suggest much of the problem lies in the mail providers being unwilling to or unable to use measures to stop spam.
I own a small webmail company (fastworks.com) and we routinely get spammed. There are a number of methods people use and a number of ways to combat them.
Spammers will go out and get a dialup account, start spamming after the ISP's abuse department has gone home (usually a Friday night) and continue until someone finally pulls the plug.
These spammers will either send the spam by connecting directly to the victim's SMTP server or by using a 3rd party relay.
We combat this by subscribing to the RSS, RBL and DUP services at mail-abuse.net.
Mail sent via a dialup connection is often denied at the outset because many dialup connections are in the DUL. Open relays are often in RBL and RSS.
These two measures alone cut out more than 80% of our incoming spam.
Another popular way (among spammers) is to try the brute force method. They connect to a service with a few million subscribers and blast away with a dictionary-type attack. This usually causes the most problems on a network side because the victim mail server has to contend with 100,000 plus bounces in a few hours. This tends to fill mail queues quite fast.
Some of the most popular mail systems (which shall remain nameless) combat this problem by not bouncing after a threshold has been reached. This, although a simple method still allows the spam to get through.
I refuse to believe that I'm any smarter (maybe faster, but not smarter) than the folks running yahoomail and hotmail, but it makes a lot more sense to me to have the delivery agent blackhole (delete) this spam as it arrives based on the source IP, email address and even the content. It doesn't take much logic to detect a host that sends you 100,000 messages in an hour where 90% of them bounce.
This cuts out 99.9% of bruteforce spam. It saves us on disk space since the spam is never delivered, and it saves on CPU cycles since the SPAM lands in /dev/null as soon as it is received rather than bouncing all over kingdom come.
I believe a very effective way to stop spam is to regulate that each ISP must specify valid SMTP servers much in the same way there is a whois database with all the DNS servers listed. If we do this, then organisations can easily choose to deny all messages coming from dialup connections and it leaves spammers with only one method of sending spam. They would have to use their local ISP's SMTP relay to get their spam out. This would be trivial for the ISP to find and shut down. It would also bring stronger incentives to monitor and stop such activity if their own SMTP servers were being hit.
Now if only we can stop ICQ spam...
-Michael