The current email spam filter is such a disappointment, I mean, they use Bayesian statistical analysis or whatever academic crap there is, but bottom line is, anti-spamming tool don't work, well they do help you cut down the number of spam emails you have to delete each day, but that's about it.
What about this for an idea:
The moment you get an email, your email server automatically replies to the address, if replying to the mailto fails, it's automatically marked as a spam. Assuming the sender gets your email, they would have to click on a URL which will track their IP, which also validates their emails. And if you don't mark this email as a spam, the sender won't ever have to verify again.