De forma de exacta no puedes identificar que una cuenta realmente exista (amenos que le envies un correo y si este no rebota, haga click sobre un enlace, etc.) y el problema que tiene el muchacho es ese, que ha realizado mucho envios de verificación a cuentas que no existen.
Entonces no le quedan mas remedios que verificar que el dominio del correo exista, tenga un registro mx, que el usuario no realice floods,etc.
De todas formas, si tu proveedor de hosting no te deja usar el smtp del servidor, utiliza uno externo (de tu isp,gmail,etc.) y eso lo puede hacer con
PEAR:Mail o Phpmailer.
Para verificar que un dominio tenga un registro mx en sus dns utiliza la función getmxrr
Código PHP:
if ( getmxrr ( "gmail.com" , $mxhosts ) )
{
echo "Dominio tiene registros MX";
print_r( $mxhosts );
}
else
{
echo "El dominio no cuenta con registros mx";
}