Problem sending to Lotus Domino 4 Domain

Hi all, I am running E2K SP 3 and I am having a small problem sending messages to organisations that run lotus Domino or Notes R4.
If a user from my organisation sends a message to the Lotus domain using OWA the recipient will recieve a garbled message – however if they use the full Outlook client – everything is ok.
I am not running any form of notes connector and all messages are relayed through SMTP as plain text.