I think there are a couple of ways ISPs can reduce the problem of spam. For starters, charge users per email past a certain reasonable amount (maybe a few hundred) per month. With regular mail you pay per piece. Why not with email? This would allow most people to still send their normal amount of emails but force the spammers who send millions each month to pay or to simply not send them. Sure, they could get around this by opening a bunch of accounts under different names with different or even the same ISP, but if all ISPs had the same policy they would end up paying whatever the ISP's monthly fee is per every few hundred emails. Since the success rate on spam is so low, the only way it is profitable is if it costs virtually nothing per email. This policy would take the profit out of it.
Next, ISPs and free email providers could block the addresses of known spammers and more important not deliver any email that doesn't have the correct email address in the "To:" field. I don't see why either is so hard to do, especially the latter which involves a simple check of the "To:" field. Yahoo for example seems to do a pretty good job blocking spam. I generally get only about 15 or so unsolicited emails a month, although about two years ago I was only getting one or two.
Finally, yes, make spam illegal, prosecute and/or file civil suits against those who send it. Try to get all countries who wish to be our trading partners to do likewise. Block emails from any countries who refuse to adopt these policies. Combined, these things can rid us of almost all spam very quickly.
It needs to be said that spam wouldn't have even continued if not for the idiots who buy from it. When you get spam, even if it's for something you're interested in, don't buy from them on principle. Those who send spam need to learn that it, like telemarketing, is a completely unacceptable way to advertise their products. Perhaps a centralized marketing exchange where everyone can advertise their wares on the Internet might be a good idea. Frankly, I see anything other than printed ads, commerce exchanges, and company websites as unacceptable ways to advertise. TV commercials are another thing I find totally obnoxious.
On another note, so-called privacy policies need to be changed. I'm sick and tired of having to send in the same forms (at my expense) every single year to be taken off the advertising lists of my bank's "associates". And even at that, they're still free to give my name to some of their "selected associates". The rule should be that unless you give permission otherwise, a business is not allowed to share your name with anyone. The Direct Marketing Association is one good reason I'm buying more and more of what I need on eBay. At least I know that if I need one thing and one thing only from someone I won't be pestered with catalogs from a million "related" businesses with things I have absolutely no interest in buying. Businesses are complaining that things will grind to a halt if name sharinig wasn't allowed? Well, if I have a news flash for them-it's grinding to a halt, from me anyway, because sharing is allowed.