Our IP address was blacklisted on the CBL due to an infection of one of the machines. Apparently CBL detected a trojan on our network, trying to connect to other machines via UDP. So, even though our network was not sending spam, CBL blacklisted the ip address.
First, PB changed the IP address of outgoing http and connections other than mail, to another ip address which he had available. Then, CBL blacklisted the new ip, with the additional info that no spam was detected, only the presence of the trojan:
IP Address x.y.z.a is listed in the CBL. It appears to be infected with a spam sending trojan, proxy or some other form of botnet.
It was last detected at 2013-10-17 11:00 GMT (+/- 30 minutes), approximately 16 hours, 30 minutes ago.
This IP address is infected with, or is NATting for a machine infected with the ZeroAccess botnet, also known as Sirefef. More information can be found from Wikipedia. It is most often used for bitcoin mining or click fraud, but as it contains a downloader portion, it can do anything.
If this IP address is a NAT gateway, it should be possible to find which computer on your internal network is infected by implementing a filter on your firewall to detect and log attempts to send UDP packets to the Internet with a destination port number of 16471.
In Cyberoam, System -> Diagnostics -> Connection List tab, port number of 16471 was seen in the destination section. That machine was cleaned up using Norton Power Eraser as recommended by CBL. Issue resolved for now.