To prevent being blacklisted in the future, allow only authorized SMTP servers on the Customer's network to send email (which, I believe, you've already done with the "Restricted firewall..." bit), be sure you're not an open relay, and encourage the Customer not to send unsolicited commercial emails that could be considered spam.
I'm guessing that the Customer got malicious software on a computer that was sending email, and since their computers all could source SMTP to the Internet the malware was able to deliver the emails it was generating.
I'd sniff traffic behind the firewall, bound for the firewall, looking for outbound SYN requests to the Internet on TCP port 25. That might find your culprit machine(s), assuming the malware hasn't figured out what you've done and "gone silent". Wireshark or other sniffer software will do what you need there.
This isn't really an email blacklisting problem, I'm guessing. It's a "users are running as 'Administrator' and allowing malicious third parties to use their computers" problem, I would guess, at the root.