Es un caso que debido a diversos motivos podría darse, sin embargo aparte de revisar tus logs, la cola de referidos y usar mailq de vez en cuando para ver que es lo que está pasando, para saber si tu servidor de correo es considerado spam o algún otro servidor ( del cual no tienes acceso administrativo o a los logs ) puedes usar este par de herramientas web, las cuales revisan entre las diversas listas negras ( blacklist ) si tu servidor esta rayado ( Disculpen el Venezolanismo 😀 ).
La primera viene del sitio web de openrbl, para citar un ejemplo, vamos a revisar el MTA de cantv.net ( relay.cantv.net ):
http://openrbl.org/client/#200.44.32.36
Esta herramienta web, verifica en diferentes listas negras de una vez por lo cual resulta muy completa esta búsqueda, al momento el relay de cantv aparece positivamente en lista negra de Fiveten.
La segunda herramienta, más que todo es el único sitio realmente importante que openrbl no revisa y es la lista de trend micro ( la cual es muy usada ) y volvemos a usar el MTA de cantv.net como conejillo de indias:
http://mail-abuse.com/cgi-bin/lookup?ip_address=200.44.32.36
En este caso, el relay de cantv.net paso la prueba y es considerado limpio.
El proceso para eliminar tu servidor de alguna de esas listas en algunos casos es tedioso como por ejemplo con la gente de trendmicro, así que procura revisar tu servidor frecuentemente y estar al tanto de la cuenta postmaster de tu dominio de correo.
saludos, me ha ocurrido este problema como 2 veces, y realmente nunca pude contactar a cantv que al menos me cambiara a otro segmento porque reiniciando por mas que cambiaba de MAC la NIC, siempre tomaba casi una ip en lista negra y peor luego trendmicro coloco el servidor .com del los buzones en lista negra, la solucion que pude conseguir fue alquilar un smtp y hasta ahora todo bien
Es el camino, realmente montar un servicio de correo con direcciones IP dinámicas no es recomendable y casi imposible, lo recomendable es usar direcciones ip fijas con conexiones corporativas, solo que no puedes garantizar que tu ISP te de direcciones ip sanas, por eso es más recomendable usar un smtp externo, hoy en día puedes montar uno por muy poco dinero usando los VPS de digital ocean y que funcionan tremendo:
https://www.digitalocean.com/?refcode=8397103400c5