You're barking up the wrong tree. The better way to stop spam is by filtering them out in other ways from the form. If you are not a fan of CAPTCHAs like reCAPTCHA, you should look into what is known as "Honeypots". Essentially, add an extra field to your form with a common name like "email" and hide it with CSS. Mark it as "leave blank" for anyone browsing with styles disabled. If the field has a value in it, it is most likely a bot, so throw the submission out. Voila. They work really well for your average mid-size website that spammers don't really care to specifically set out to beat. Check out this related question.
All things considered, I like the honeypots because it is usually enough to deter 99% of your spamming while not making your average user have to do anything. This is important.
To quickly answer your original question: the only way to verify the email is valid is to actually send out an email to that address and see if it bounces. It is generally not worth the hassle, however.