Seems like everyone and their brother has published one of these. We're doing the same, combining two different methods we've seen. A regular expression to match most email addresses, exotic ones would likely be missed. Then a dns lookup is done, to validate their domain.

function is_valid_email($mail)
{
    // Match Email Address Pattern
    if (preg_match('/^([\w\.\%\+\-]+)@([a-z0-9\.\-]+\.[a-z]{2,6})$/i',trim($mail),$m)) {
        // More strict is to only check MX, we do both in example
        if ( (checkdnsrr($m[2],'MX') == true) || (checkdnsrr($m[2],'A') == true) ) {
            // host found!
            return true;
        }
    }
    return false;
}