El problema puede ser casi con seguridad, que tu IP esté incluida en alguna lista negra, y los destinatarios que reciben o no tu correo, estén utilizando una de estas listas para filtrar el spam.
Verifica en la cuenta admin via webmail de tu servidor, si hay mensajes rebotados, y cuál es su causa. Si llegaras a estar en alguna lista y tienes IP dinamica, solo reinicia el servidor para que cambie la IP. Si es fija debes hablar con tu proveedor de internet para que pueda realizar el trámite de desliste de tu IP. Solo el ISP puede realizar dicho trámite ante los sevicios de black-lists
No envies correo spam, o asegúrate que ninguna maquina en tu LAN lo este haciendo, ya sea voluntariamente o porque este infectada.
Lee en el WIKI toda la seccion
http://wiki.contribs.org/Email