Outlook Express is not the client of choice with Exchange server. When you pull mail from the Exchange server with Outlook Express, you are using the POP format. The typical behavior with POP is that each message is deleted from the server after it is downloaded. Outlook (97, 98 or 2000) is a better choice.
Having said that, your problem using Outlook Express is probably in where the messages are being stored. Each user has a message store, which is, by default, in the user's profile. You will have to check whether in your environment this is on the C: disk or on the network (local copy or net copy.) This is controlled in Outlook Express in Tools/Options/Maintenance/Store Folder.
If you have roaming profiles, and everything goes well, everything works.
What happens when a user has a problem getting to the server at login time and a cached profile is used? If the user collects mail, that mail is merged into the old (cached) copy of his message store, which may days or weeks old depending on when the user last used that computer. When the user logs out, if the profile is written back to the server, the new (old with new messages) message store is written over the copy on the server, losing all messages between the cache time and now. If the new message store is not used to update the server, today's messages vanish into the bit bucket.
Things you can do:
Make each user message store point directly at its location, using an UNC address. Make this location in the user's home directory on the server, not in his profile.
Switch to Outlook, which eliminates this problem.
Good luck.