I have a similiar situation.
I have a mix of NT4 workstations (mostly SP6a with various hotfixes and security patches) and W2k Pro workstations (mostly SP2 with various hotfixes and security patches). All of the NT and most of the W2k machines are running Office 2000 (SP-1 with various levels hotfixes) with Outlook 2000 as their mail client. I also have some W2k machines running Office XP (pre-SP1) using Outlook 2002 as their client.
It seems that after I began updating browsers to IE6 and applying the patch (Q316059), problems started to emerge. Outlook 2000 clients are receiving truncated messages from Outlook 2002 clients. Long messages with a series of forwards and replies get truncated somewhere in the middle (exactly where seems to depend on the length and size of the message). The receivers (and the senders) do not know the messages have been cut off and are only aware of the problem when somebody who knows about the missing text or the message is cut off mid-sentence.
The problem seems to occur when the Outlook 2002 (XP) client sends the message as HTML. When the receiver's mailbox is viewed from a machine with Outlook 2002, the truncated portion of the message is magically visible and the whole message text is present as if nothing is wrong. When the exact same message is sent as Rich Text or Plain Text by the Outlook 2002 client, everybody, regardless of client (XP or 2000 and W2k or NT) can view and read all of the message. It appears that the entire message is sent, but is just not available for viewing on some clients. It seems to effect NT workstations with the greatest vengence.
One possible solution concerns the file "mlang.dll" Make sure that that all your computers are on the sameversion. The latest version is 6.0.2600.
This might clear up your problem. Unfortunately, it did not clear up mine. I am still looking.
