Lo primero es revisar los logs, ya que dependiendo de la CBL, además de decirte porque te banean, generalmente te indican la hora aproximada del evento.

Con hora en mano, vas y revisas los logs, en un período +/- 5 min y créeme uno que es necio porque allí en los logs es donde uno debe iniciar.

A mi no me gusta usar el puerto 25 para que mis usuarios envíen correo, para eso está el 587 y el 465. Así que la sugerencia de DeathUser es un imperativo que no deberías ignorar.

La cola de correos también es un buen lugar donde encontrar evidencia, especialmente cuando hay spamtraps de por medio.

Hay una herramienta que se llama pflogsumm, es muy útil ya que te genera un reporte que te permite detectar de manera más fácil algún problema.

Hazle pruebas de openrelay también, conectate via telnet al puerto 25 y sin autenticar trata de enviar correo a hotmail, yahoo, etc, si tu server está bien configurado no te debe permitir hacer esto.

Te cuento una anécdota, hace unas semanas me tope con un caso en que la ip de un mail server fue baneada, y luego de buscar en los logs se encontró que la contraseña de un usuario de la organización había sido comprometida, y que el spammer envíaba correo conectándose con credenciales reales y allí la moraleja: de nada sirve un server bien configurado si los usuarios usan contraseñas débiles.

Un último consejo: Los problemas no se arreglan mágicamente, es necesario descubrir la causa y solucionarla, así que pilas revisa hasta dar con la causa y tener un entendimiento claro de lo que sucedió.