You can't really verify that unless you actually try and send them an e-mail. Most mail servers will give a positive response to any VRFY request, or not respond at all. Some spam comes with a valid FROM: address, except it isn't theirs. Some commercial spammers will run their own servers, and have a server to accept and bit-bucket the bounces. Personally, I think the best approach is to have a bounty on spammers.
There's no barrier on sending them an email, so it isn't like that's a big hurdle.
Every email that you receive should come from a previsously verified email address (e.g. friends, businesses, family). Emails that are NOT from already verified addresses SHOULD be verified automatically by your spam filter.
That's easy to do. Send a real email to any "unknown" sender, and ask that they make a certain type of reply (on-line, web, email, message) if they want their message to be passed on to you. If there is a real person who wants to communicate with you, then they will verify themselves, but stolen email addresses and invalid email addresses (which is what spammers use) clearly won't be able to get onto your list of verified email addresses.
And people only have to get verified (to send email to you) one time. After that they are then on your list so that all future emails from them to you go through normally.