Aqui vai uma simples função php para verificar se um e-mail é válido ou não, com esta função estamos verificando se o nome do usuário possui caracteres válidos e se o host deste e-mail existe com a função checkdnsrr.

<?php
	function validaEmail($email) {
 
		$expressao = "^[a-z\'0-9]+([._-][a-z\'0-9]+)*@([a-z0-9]+([._-][a-z0-9]+))+$";
 
		if( eregi( $expressao, $email ) ) {
			return checkdnsrr(array_pop(explode("@", $email)), "MX");			
		} else {
			return false;
		}
	}
?>

Nota: (checkdnsrr) Esta função não é implementada para plataforma windows, mas existe outros meios para windows basta conferir no manual: php.net