Hola,
Cita: he probado enviar a hotmail
¿Has mirado en la carpeta de correo no deseado? Normalmente los emails enviados con mail() (sin hacer nada mas, normalmente por culpa de los admin de los servidores) suelen ser tomados como spam.
Segundo, mail() devuelve false si se ha producido algun error al pasar el correo a sendmail o al smtp. Verifica el valor devuelto en tu caso.
saludos.