Bien, al final hemos encontrado el fallo. El rDNS estaba correcto, representa que sólo hay una entrada y debes crear una entrada PTR para cada dominio.
El problema venía de un dia que intentamos migrar otro dominio ( que es el que utilizamos actualemente ) pero no se terminó de migrar, solamente era para hacer pruebas pero quedó entrado el dominio en el Plesk y sus entradas de DNS, con lo cual, al enviar desde la misma maquina se intentava enviar al dominio que había alojado dentro y por eso no llegaba.
Total, hemos eliminado la entrada de este dominio y todo ok... en fin, gracias por todo!
Ah! Y sobre el Serverloft no tenemos queja, sólo que NO hay soporte en Español. Primero contactamos con un comercial que medio hablaba portugués-español y nos dijo que si había soporte en Español, pero cuando enviamos Tickets sólo los puedes enviar en inglés sino no te entienden. Por lo demás son bastante eficientes y te responden muy rapido incluso los domingos.
Quizá con el tema del reverse DNS hubiese venido bién que nos hubiéran comentado como funcionava, pero ellos solo te dan soporte para hardware y poco mas.
Un saludo!