One thing I started doing many years ago (maybe 7ish) was to give a different email address to everyone who requested one. That way, when I started getting spam, I'd know who it was from. So far, the only site to have ever sold my email address was Uproar.com. Much of my spam unfortunately seems to come from addresses harvested from peoples' infected machines; addresses that I've only used to send replies to tech support requests get tons of spam. All of my mail at my domain goes to a single account, and I filter it locally on my home computer in Outlook.
Unfortunately, this plan has backfired. Where at first it was a resounding success it is now an obnoxious failure. A couple years ago, spammers realized that since spam is free, the "shotgun" approach works just fine—they can have great success by just picking random usernames and appending them to a domain name. So, I get thousands of spam mails a day, addressed to addresses that neither I nor anyone else in the world has ever had an account at. Just as bad, I also get thousands of non-delivery reports for spam mail I never sent using more made-up account names as the From: address.
I need to come up with a solution. Probably what I'll need to do is to come up with a few account names that I really want to keep (such as anything that contains the word "travis"), and then delete everything else that comes into my mailbox. It should be feasible to get this right. Gmail has one of the coolest solutions to this problem for "normal people" that I'm aware of—you can give people addresses like [email protected], and mail sent to that address will go to myusername's inbox, tagged with the mytag tag. That way, you can do exactly what I do currently and have essentially infinite accounts, but still not get mail addressed to random account names. The drawback is that if a lot of people start using that feature, it would be extremely easy for spammers to just strip off the "+" portion of the address, basically converting a "spam-safe" address into your real one. Another drawback to both Gmail's solution and mine is that occasionally I forget exactly what variation of my address I used at any given site. Did I give Amazon.com "travis", "travisamazon", "travisaz", or something else?
Providing a way for people to easily manage all of the different email aliases they give out to people could be a "big win" for Gmail, or anyone else who implements similar features. Spam filtering will continue to improve, but making it more convenient for people to use aliases could be a lot more effective.