Well actually we just need to add some additional security checks in relation to spam mail being generated from an Exchange 2003 server. In this case we used wireshark to identify where the traffic was coming from and then locked the exchange server down further to make sure it could not be used to generate any more messages from non authenticated sources.
The odd behaviour – ie small amounts of spam were unusual. Working with CBL to get to the root of the issue was slow due to the lack of evidence we could find. Ultimately though the changes to security and the complexity of mail enabled apps in the origanisation were overcome to ensure no more blacklisting for this client.
However an abject lesson in tracking and identifying the source of these unapproved mails.