A hotmail siempre le han caido mal muchos mails enviados directamente desde páginas web nose por que, si te fijas en muchas páginas web recomiendan no utilizar hotmail para crear una cuenta de usuario por ejemplo, yo no he tenido en principio problemas de este tipo, por ejemplo he usado estos headers:
$headers = "From:
[email protected]\nReply-To:
[email protected]\nX-Mailer: PHP/" . phpversion();
Son mucho menos complejos que los que tu utilizas, pero pruebalos a ver si va a ser algo de los headers y si es asi despues vete descartando a ver que es.
Saludos.