Si cumples los requisitos de que tu servidor bajo PHP en dominioX.tal y el "FROM" que dices ser en la composición de tu e-mail es del mismo dominoX.tal que lo envia .. No deberías tener tantos problemas en que sea clasificado tu e-mail como SPAM.
De todas formas, .. cada proveedor filtra los e-mails a su convenencia, .. algunas veces con mejor o peor criterio (reglas de mensajes). Si aplica alguna regla por "dominos" .. con PHP nunca podras solventar ese prebla .. si lo hace por "palabras que encuentre en tu e-mail o asunto" .. lo mismo ..
Otra cosa que deberías revisar es que tus dominos no estén en listas negras ya clasificados como SPAM y que muchos filtros de anti-spam se nutren (o consultan mejor dicho) para verificar que un dominio sea "valido" (o esté "limpio" de haber hecho SPAM).
Sólo te recomendaría generar un e-mail con el formato correcto que las RFC's que definen el protocolo SMTP así lo definen.
Te podría recomendar probar con la classe:
PHPMailer
http://phpmailer.sourceforge.net
La cual "dice" implementar lo más posible lo que las RFC's dictan sobre emisión de un e-mail. Pruebalo y nos comentas.
Un saludo,