No creo que mail() de php no envie a hotmail, eso es aleatorio y no tiene sentido. Mi idea es que hotmail filtra tus correos por que desconoce el origen.
La solución que yo uso es usar Gmail o Homtail o Yahoo! para enviar los correos. Uso una clase de conexión SMTP y los envío. Así no te los rechazan.
No se si PHPMailer tiene la opción de enviar por SMTP, PEAR Mail si lo tiene, y si no, hay bastantes clases libres que permiten el uso de SMTP. Yo tengo una:
Clase Amailer