Hi,
In case anyone else comes across this problem, I am posting a solution that MessageLabs came up with for us after a week of banging my head off the wall...
The problem was that emails to certain domains were getting stuck in our outbound SMTP queue on our Exchange 2003 server, which uses MessageLabs as a Smarthost to viruscheck/antispam check etc (less overhead on our server). MessageLabs suggested that I install a packet trace on the email server, only for port 25 and to send them the logs. It transpires that some emails had a problem in the signature (that Exclaimer puts in) where there is an extra space AFTER a dot, which is an End Of Data signal. So MessageLabs were never getting the End Of Data character and were holding the SMTP queue open for 4 minutes before terminating it. The Exchange server would simply try to send the message again so that the queue was always staying active.
As I had not edited the signature in nearly a year with Exclaimer, this was somewhat bemusing, but what I HAD done was to upgrade Exclaimer Mail Utilities to version 4.56, which, although it uses the same disclaimer that we had with the previous version, something must have been changed in the upgrade process that has put in an extra space in the text.
The resolution was pretty simple in that I simply recreated the disclaimer in Exclaimer and now it all works fine!