Hola,
PHP no "envia" el mensaje. Solo se lo pasa al servidor SMTP o al programa sendmail (en *nix). Si mail() devuelve true, es que se lo ha pasado con exito al servidor SMTP o al sendmail. Nada mas. Que ese email llegue a su destino depende de multitud de variables. Cualquier fallo o filtro antispam/antivirus/seguridad que haya entre tu SMTP o tu sendmail, y la bandeja de destino, puede eliminar tu email y hacer que no llege a su destino. Yo incluso he recibido emails un par de semanas despues de que se enviase (¿donde habra estado?
¿donde estaran todos los emails que se pierden?
¿en el cielo de los emails?
).
Prueba con otras direcciones de correo (sobre todo procura que no sean de hotmail). Si te llega a una cuenta, el problema no esta en la salida (tu script y tu SMTP), si no en la recepcion (la cuenta destino). Probablemente algun filtro antispam. En el foro ya se ha comentado algun metodo para "saltarse" los filtros antispam. Busca por "antispam" o "spam".
Suerte.