To me, spam is not such a hard problem to solve. I think that within a few years, spam email will no longer be a problem and ultimately, the solution will be more technical than legal, but likely a combination of both. Consider these approaches:
(1) Whitelisting: Already available on Hotmail. You can choose to receive emails only from "whitelisted" addresses, e.g. your addressbook. This is an extreme solution, so I dont think many people use it. I heard from a friend at Microsoft that the next version of Outlook will support whitelisting as well. If you think about it, adding known addresses to your addressbook is really a win-win. You can use shortcuts when you send email and it also blocks spam.
(2) Challenge and Response: Any email not from a whitelisted address is "challenged." You never see the email unless the challege, probably a CAPTCHA of some sort, is completed successfully. I love CAPTCHAs. They are neat. Yahoo already uses them for creation of new accounts. Check out CAPTCHAs here:
http://www.captcha.net/(3) Server-side hardware and software: If you work at a big company, like say, Morgan Stanley, you're probably already benefiting from specialized hardware and software on the server side that filters out spam mail. There are bunch of companies that now build "anti-spam" boxes. That's all they do. Common players are Brightmail and CypherTrust, but there are a bunch.
Lastly, I'd like to add that the end-user is also becoming "smarter," or at least more techno-socially responsible. A lot of people wont post their email addresses on blogs and such, so that the address doesn't get "scraped." Also, if I'm ordering stuff online from a not-fully-trusted retailer (e.g. Amazon), I wont give them my email address, because I now know that they'll just turn around and sell it. (For example, www.smartinventions.com sells stuff that are "Seen on TV." They are legit, but I also learned the hard lesson that they sell my email address and phone number. Nice additional revenue stream for them.)
Help on the legislation side would be nice, but (a) legislators are hardly tech-saavy, (b) the legislation process cant keep up with technology changes, (c) enforcement is an issue (e.g. moving your spam server to another country).