StrikeIron offers an Email Verification Web Service (can be easily integrated into applications, business processes and Web sites via SOAP and REST) that for the most part identifies whether or not an email address is a valid one (it exists and can receive email) without actually sending an email.
We use a series of "secret sauce" algorithms running in parallel across the Web, including some things like domain name existence checking, MX record analysis, SMTP conversations, and several other series of redundant checks to make this work.
Email verification/validation is important not only to filter out bogus email addresses, but also to stop sending email (such as newsletters) to email addresses that no longer exist (typically because someone no longer works at a company).
There are a broad range of benefits for this kind of capability, such as keeping off spam lists from mass emailing to non-working addresses, optimizing the time of a sales team by filtering out phantom leads, identity verification, and also triggering reach outs to contact lists when an invalid email address indicates that a current contact is no longer with a company. This last one can be important for several departments, including accounting/collections, sales, and marketing.
We have also done an integration of the capability into Salesforce.com to make the email validation process within Salesforce seamless and very simple to turn on.
A simple concept, with a complex behind-the-scenes process, can be a big help on the path to success.