Just an update:
We found the cause in the end by "normal" means; we scanned the right PC and found the trojan that was causing the problem. Never quite worked out which trojan it was (the machine had several) but it hadn't been on the network when we first looked because it was the boss's laptop. (Isn't it always?)
Now that we have cleared the problem their IP address has been removed from the blacklists, although that's not a problem now as we configured their mail server (Exchange - horrible thing) to send via the ISP's smart host.
This got me thinking: Are there any voluntary blocklists where you can subscribe IPs that should never send any email, and so any email from that IP should be assumed to be spam?