É impossível fazer uma validação definitiva de um endereço de email porque muitos servidores de SMTP de destino aceitam mensagens mesmo para endereços que não existem, e talvez só depois retornam uma mensagem para um remetente informando que o email não é válido.
No entanto o que você pode fazer é simular o envio de uma mensagem para o dado endereço de email e ver se o servidor de SMTP de destino aceitaria o destinatário.
Para isso precisa consultar o DNS para obter o registro MX do domínio informado e assim saber qual é o servidor ou quais são os servidores que receberiam a mensagem para esse domínio. Pode dar 1 servidor, vários ou até nenhum. Neste último caso o servidor a ser usado deve ser o do registro A do domínio.
Aí conecta na porta 25 de cada um dos servidores. Se um deles já recusar o destinatário, você já fica sabendo que é inválido. Se um deles aceitar, já fica sabendo que é válido. Se nenhum servidor aceitar a conexão ou der um erro com código 4XX, não dá para saber se é válido, pois é uma situação que pode ser temporária.
Implementar este algoritmo de forma adequada é um pouco trabalhoso. No entanto eu mesmo desenvolvi uma classe de PHP para validação de email que já implementa esses passos todos e tem sido aprimorada desde 1999.
Para além disso a classe ainda permite que você defina uma lista de domínios que você nunca vai querer aceitar emails, como aqueles de emails temporários descartáveis.