Quick answer: You can't.
Beyond basic syntax checking, which "gfdhfgd@hjhgfdh.com"
would pass, there are tools to check the existence of the domain
and the presence of a mail server via DNS. But some spammers have
this figured out and will send you "gfdhfgd@msn.com". Due to
spammers again, most email servers have email account verification
services blocked so the only way to validate an email address on a
valid email server is to send a message and wait for a user
response.
My solution would be to make spamming a capital offense, but
I think I would meet some resistance promoting this line of
defense!