Pour éviter d'être mis sur liste noire à l'avenir, n'autorisez que les serveurs SMTP autorisés sur le réseau du client à envoyer des e-mails (ce que, je crois, vous avez déjà fait avec la partie "Pare-feu restreint..."), assurez-vous de ne pas être un relais ouvert et encouragez le client à ne pas envoyer d'e-mails commerciaux non sollicités qui pourraient être considérés comme du spam.
Je suppose que le client a installé un logiciel malveillant sur un ordinateur qui envoyait des courriels et que, comme tous ses ordinateurs pouvaient utiliser le protocole SMTP pour se connecter à Internet, le logiciel malveillant a pu transmettre les courriels qu'il générait.
Je reniflerais le trafic derrière le pare-feu, à destination du pare-feu, à la recherche de requêtes SYN sortantes vers Internet sur le port TCP 25. Cela pourrait permettre de trouver la ou les machines coupables, en supposant que le malware n'a pas compris ce que vous avez fait et n'est pas devenu silencieux. Wireshark ou un autre logiciel renifleur fera ce dont vous avez besoin.
Il ne s'agit pas vraiment d'un problème de liste noire d'emails, je suppose. Il s'agit plutôt d'un problème de type "les utilisateurs s'exécutent en tant qu'administrateurs et permettent à des tiers malveillants d'utiliser leurs ordinateurs", je suppose, à la base.