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.