Verificação de e-mail existente

Você pode criar um  dicionário de domínio inválidos, onde, após a submissão do formulário, você valide se o domínio não está nesta blacklist. Existe outras formas através do seu servidor de e-mail verificar  se o e-mail quando enviado é bounce (domínio válido, mas conta de e-mail inválido )  ou se é invalid_domain (Como o  nome mesmo diz,  domínio inválido), mas isto requer que você consiga, de forma inteligente, consumir este serviço integrado à sua aplicação. Este último método de verificar através do seu servidor de e-mail ainda tem uma grande falha:

• Se o usuário inserir um e-mail temporário (Através de ferramentas como tempmail.org ou dispostable.com ), você precisaria ainda de um dicionário de domínios inválidos para poder invalidar estes e-mails.

Para evitar e-mails falsos no formato que colocou (ex: teste@teste) você pode utilizar um validador de e-mail utilizando javascript e expressão regular como essa aqui:

function IsEmail(email){
    var exclude=/[^@-.w]|^[_@.-]|[._-]{2}|[@.]{2}|(@)[^@]*1/;
    var check=/@[w-]+./;
    var checkend=/.[a-zA-Z]{2,3}$/;
    if(((email.search(exclude) != -1)||(email.search(check)) == -1)||(email.search(checkend) == -1)){return false;}
    else {return true;}
}

Agora se o objetivo é ver se o e-mail existe, mesmo ele passando pelo validador, ai só se fizer o que @Phillip Parente escreveu.

o dicionário de domínios me parece inviável, pois pode invalidar emails legítimos do tipo você@suaempresa.com.br. Imagino que o ideal seja:

1) utilizar um input type=email. A utilização desse input vai elimiar a necessidade de checagem por meio de expressão regular proposta pelo @Marco Mascarenhas. Ou se preferir também pode utilizar a expressão regular pois não há nenhum problema.

<input type="email" name="email">

2) Enviar uma mensagem com um código para o email informado e só validar o cadastro caso o usuário digite o código informado no formulário.

O correto é sempre fazer a verificação server-side, pois o input do tipo email não funciona em todos os navegadores ainda. Utilize expressão regular em PHP no recebimento do formulário também.

A melhor forma mesmo de limitar isso, é limitando o cadastro do usuário, por exemplo, obrigá-lo a confirmar o seu cadastro pelo email informado. Isso certamente irá impedir de por qualquer email que não seja válido, se o usuário realmente tiver interesse no cadastro.

<?php
$exp = "#^[\w.-]+@[\w.-]+\.[a-zA-Z]{2,6}$#";
   if(preg_match($exp,'asd@a.com')){
        print 'Verdadeiro';
   }else{
          print 'falso';
   }
?>