Hola kratos91,
para validar si un correo existe, la única forma es preguntando al servidor que maneja la cuenta, para lo cual tenés que iniciar una comunicación SMTP con el servidor como si enviaras un e-mail, o más simplemente, enviando un e-mail para ahorrarte tener que implementar el protocolo.
Si la cuenta no existe, el servidor SMTP responderá indicándolo en respuesta al comando RCPT TO
. Esto an casos de que el SMTP sea un proxy puede dar siempre verdadero, pero son casos exepcionales.
Para enviar un e-mail desde Android fijate en http://sekthdroid.wordpress.com/2013/02/09/enviar-email-desde-una-activity-android/ o en http://stackoverflow.com/questions/2020088/sending-email-in-android-using-javamail-api-without-using-the-default-built-in-a en dónde se ilustran dos formas distintas de hacerlo.
Si querés ver como es la secuencia de conexión con un servidor SMTP, tenés los comandos y un ejemplo acá http://systemadmin.es/2009/01/como-mandar-un-email-con-telnet-protocolo-smtp, pero este mecanismo no es viable actualmente porque los servidores SMTP usan autentificación, TLS y varias cosas que no son texto plano.
Nota: enviar un e-mail valida que la cuenta exista, pero no que sea de quien la ingresa. Para esto tendrías que enviar un código de validación y tener un lugar en dónde el usuario lo escriba para validar que sí sea su cuenta.
Saludos!