function checkEmail($email) {
     // checks proper syntax
     if(preg_match("/^( [a-zA-Z0-9] )+( [a-zA-Z0-9\._-] )*@( [a-zA-Z0-9_-] )+( [a-zA-Z0-9\._-] +)+$/" , $email)) {
      // gets domain name
      list($username,$domain)=split('@',$email);
      // checks for if MX records in the DNS
      if(!checkdnsrr($domain, 'MX')) {
       return false;
      }
      // attempts a socket connection to mail server
      if(!fsockopen($domain,25,$errno,$errstr,30)) {
       return false;
      }
      return true;
     }
     return false;
    }

    $email = trim($_POST['email']);  
    if(!checkEmail($email)) { 
    echo 'Invalid email address!';
    }
    else {
     echo 'Email address is valid';
    }
gefunden bei http://www.devshed.com/c/a/PHP/Email-Address-Verification-with-PHP/5/ soll angeblich auch noch die Domain prüfen.