Problema con el correo asociado a un dominio

[rubensm]

Hola a todos


Tengo un problema con unas cuentas de correo, he intentado investigar por todos los lados, pero ya no se que hacer.
La verdad que no tengo ni idea de esto, pero bueno. Espero que me podais ayudar.


Tengo varias cuentas asociadas a un dominio propio. Siempre que envió desde cualquier cuenta a direcciones tipo hotmail, gmail, yahoo, van directamente a la carpeta de spam o correo no deseado.
Ya he contactado con la empresa que proporciona el dominio pensando que podría ser un problema de DNS inversa, pero parece que eso está bien.
Según ellos, han modificado el registro SPF para identificar el dominio con la IP,pero el problema sigue.
Las cuentas están en un servidor virtual dedicado, el dominio tiene la propia IP, pero todos los correos del servidor compartido se redireccionan a la misma dirección IP 65.254.32.66. Esta IP si que tiene resolución inversa.
He comprobado si las IP's están en alguna blacklist. He chequeado Spamhaus, pero no aparece nada.
He hecho un diagnostico con el nombre del dominio y devuelve algún fallo:
Relay Check: WARNING! Your server could be an open relay.
Rev DNS Check: Reverse DNS FAILED! This is a problem.

También he pensado que podría ser un problema con el registro MX, aunque de eso no estoy tan seguro.

Muchas gracias.

Un Saludo