Además de lo que te pregunta PYDOT
Cita:
Iniciado por PYDOT 
¿Tiene un propio servidor dedicad? El servidor de correo esta instalado en el mismo o utilizas un servidor de correo externo para los mails? Que servidor de correo tienes instalado?
por favor, nos dices también si los mails estos que son rebotados ¿se estan enviando desde una red de la propia Telefónica, con ADSL's de Telefónica por ejemplo, o se envían desde otros ISP's, es decir a través de mail servers de otros proveedores?
Saludos y gracias.
Nota: los problemas de resolución inversa suelen venir reflejados en el mail de vuelta con una respuesta del tipo "Remote host said: 550 Reverse DNS lookup failed for host..."