We had configured the Exchange server "IP Block LIst Providers" option to use SpamHAUS and SpamCop as the providers. The server had been functioning perfectly for quite a while with these settings, until yesterday that is. For an unknown reason, virutally all email was no longer being received and we started getting calls from the intended recipents stating that they were getting rejection notification emails. Through trial and error, I found that disabling SpamCop as a provider in Exchange permitted email to be delivered to the recipients again. After this, I configured a custom rejection notice to tell me the iP address of the sending mail server and the source that was reporting it as being on a block list. This morning we started getting calls from clients stating that they were getting rejection notifications again with SpamHAUS as the reporting provider.
Short story long, I found that it was an issue with Exchange and had to disable the "IP Block LIst Providers" option all together. We are not looking into alternate options such as an appliance or a third party paid service.