MS Exchange black listed with CBL

Do you receive your email directly by SMTP? If so then you need an MX record.
If you don't, then you are probably blacklisted on either lack of reverse DNS, what the machine is announcing itself as or being on a dynamic IP address.

Simon.

I'm not certain, but if you go to their site and lookup your IP (http://cbl.abuseat.org/lookup.cgi) it should provide a link with some possibilities as to why it may have been listed.

Here's another good site if you want to make sure you haven't drifted onto other blacklists as well http://www.robtex.com/rbls.html

Further to this, the x.x.x.185 is being  reported as cbl listed. Which is the router and not MS Exchange. Is it possible that a workstation is sending out spam or causing the problem of the public ip x.x.x.185 as being cbl listed. The router has nat enabled and any address within the network from x.x.x.50 to x.x.x.100 is mapped to the x.x.x.185 public ip address of the router.

Very likely. I saw this just last week....a client's laptop had a worm that was sending spam - it didn't take too long for the external IP address of their firewall to get blacklisted with CBL. (the person had travelled to a branch office and got their firewall's IP blacklisted as well =)

I'd use some sort of packet sniffer on the internal network and see if any workstations are creating a lot of traffic.