As noted above, most email servers shut down the VRFY command since it is prone to email harvesting from spammers.
There are a few options for verifying email addresses
1) Use an email verification link. This can cause a drop in conversion rate as potentially get your email sender (either you or an ESP who will complain at you) in trouble if you are sending too many verification emails that bounce. If you have any deliverability issues, the links will end up in the spam/bulk folder and never get clicked. I am not a big fan of this approach if you care about conversion and/or support tickets. I did some research on this a while back and wrote a blog entry if you are interested: http://blog.strikeiron.com/bid/54483/Email-Verification-Links-Kill-Your-Conversion-Rate
2) Use a paid tool. These come in 3 flavors
a) real-time API - there are companies (full disclosure, mine is one of the companies in this space) that offer paid solutions are able to verify emails in realtime with high (>95%) accuracy.
b) database lookup vendors - this is another paid option where the collected email is compared against a database. Generally less expensive but not as accurate as real-time
c) tools for your PC - avoid this. They are not accurate and will get your IP address blacklisted.
3) Do a quick check (regex, check for a MX server, etc) and accept ambiguous emails as valid. Depending on your volume and audience, this might be a good option.
Hope this helps.
Justin