I got a call from Network Security saying that our mail server was reporting to an ehlo command that its name was localhost.localdomain. This isn’t really a problem, except that some spam-reporting companies have a bug where this would be enough to automatically blacklist our machine. I edited /etc/hosts and added our machine there, restarted sendmail and everything looks ok.
Also, you have to go to the spamhaus website and request that the address be removed from their system. What a pain!