Both the malware and spam problems are a kind of tax on the overall internet population caused by the least sophisticated users (I won't reference IQ here, but there is certainly a correlation). It's the least sophisticated users that tend to get their machines infected (providing cheap botnet spam distribution -- any pc with a broadband connection can send out millions of messages per day), and it's the least sophisticated among us who reply to spam messages, generating profits for the spammers. I suspect that removing the 20% least sophisticated users from the ecosystem would make life 10 times harder for the bad guys.
Perhaps instead of trying to attack the problem by going after spammers, what we should be doing is going after the woodheads. It is almost impossible to enforce a law against sending spam. So we should try to pass a law against responding to spam.
What I propose is that any American who makes a purchase based on unsolicited email be fined $10,000 and jailed for 30 days. The law would be enforced by undertaking random audits of companies that are successful at attracting business by using spam. The law would be highly publicized by internet service providers and corporate CIO's, who have a strong interest in reducing the volume of spam. Thus, everyone with an Internet account would be on notice that purchasing from a spammer can get you in trouble.
If we can deter Americans from responding to spam, then spammers will stop routing spam to domains in the U.S. That's my solution.