No sólo las cabeceras deben ser lo más extrictas posibles que cumplan con las especificaciones de las RFC's correspondientes (SMTP) .. también hay otros aspectos sobre las conexión que se usa (IP, domino .. etc) para enviar el e-mail en si (la de tu MTA .. no de PHP en sí aunque suele suceder que el servidor SMTP o MTA en general y PHP conviven en el mismo Servidor).
Puedes leer algo al respecto:
Sobre los filtros anti-spam que implementó Hotmail y otros proveedores de servicios de e-mail:
http://www.ironport.com/pdf/ironport_2004-05-05.pdf
Un saludo,