I’m using my blog today as book mark service today.
I just found this article on howto really validate if an email address exists.
I’ll have a go at wrapping this article into a WCF/Webservice
http://www.webdigi.co.uk/blog/2009/how-to-check-if-an-email-address-exists-without-sending-an-email/