você menciona os registros SPF e TXT, mas o DNS direto e reverso também precisa estar correto.
edit: maneira mais fácil que eu sei testar:
dig -x +short 'dig +short your.domain.com'
Isso deve retornar "your.domain.com". Se isso não acontecer, separe os dois comandos:
dig your.domain.com
dig -x your.ip.address
para ver qual ou ambos não estão funcionando corretamente.