Para impedir a inclusão de listas negras no futuro, permita que apenas servidores SMTP autorizados na rede do Cliente enviem e-mails (que, acredito, você já fez com o bit "Restricted firewall ..."), certifique-se de ' não é uma transmissão aberta e incentiva o Cliente a não enviar e-mails comerciais não solicitados que possam ser considerados spam.
Suponho que o Cliente tenha um software mal-intencionado em um computador que estava enviando e-mail e, como todos os computadores deles podiam enviar SMTP para a Internet, o malware conseguiu entregar os e-mails que estava gerando.
Eu farejaria o tráfego por trás do firewall, com destino ao firewall, procurando por solicitações SYN de saída para a Internet na porta TCP 25. Isso poderia encontrar sua (s) máquina (s) culpada (s), supondo que o malware não tenha descoberto o que você já fiz e "ficou em silêncio". O Wireshark ou outro software farejador fará o que você precisa lá.
Isso não é realmente um problema de lista negra de e-mail, eu estou supondo. É um "usuários estão executando como 'Administrador' e permitindo que terceiros maliciosos usem seus computadores" problema, eu diria, na raiz.