Strange Issue (Email Attachment Corruptions) Please help!

Well im sick of banging my head against this one. Hopefully someone can help.

We are getting corrupted email attachments in our network from our mail server. This happens at random, meaning that the same email with the same attachment will corrupt on one system and not on another. Although the same attachment can be opened within web mail.

Now here is the twist. We have moved the mail server to another host and yet we get the same result. But if we check the mail from outside of the network (ie. at home) we can open all attachments without fail. We also set up a mirrored mail account on another mail server on another network in another part of the world and all works fine.

This behavior seems to not be OS related since this is happing on a wide spectrum of clients (98, ME, 2000, and XP) and it does not seem to be related to the version of office running or Outlook Express. Also happened when I installed Netscape, so not MS specific.

The mail server is currently residing on a win2k server that is up to date and clean and for all other purposes works fine.

A little help would be greatly appreciated.
TIA