Are you Outlook Express clients up-to-date?
Yes, we have WSUS, all the patches all approved and installed. We don't have
IE 7 yet so I don't know it resolves the problem. It looks to be a OE 6
specific problem

And who is reporting the time out? The client or the server?
The client is reporting the timeout. By telnetting or even with Mozilla
Thundrbird client there are no problems with the reception of the malformed
message.

And are the client PCs running any anti-spam or anti-virus set to scan
e-mail? If so, either of those could cause the time out.
The client PC no. But the Exchange server is running ExchangeSecure 2006
from Panda Enterprisecure suite. The malformed message was "touched" by the
antivirus because it replaced the actual content with a text informing that
"Panda Antivirus have found a vulnerability in the message". It is possible
it was Panda that malformed the message when cleaning it.

Thanks for your attention
Sammy