Hola,
También debes confirmar que exista un registro DNS inverso (rDNS) para la IP desde la cual envías los correos.
También deberías confirmar que la dirección IP desde la que envías los mensajes NO se encuentre en alguna "lista negra" (blacklist) anti-spam. Puedes confirmarlo desde este sitio:
http://www.dnsstuff.com/tools/ip4r.ch?ip=
Y también debes procurar agregar un registro SPF en la zona DNS de tu dominio. Encuentras más información aquí:
http://www.openspf.org/wizard.html
Saludos!