You have little knowledge of Outlook and I have zero knowledge of Exchange. Fine pair we make, eh? I'm really hoping one of the Exchange experts will step in to help here, because there may well be some settings in Exchange that would be creating your situation.
In the mean time, let's look at the Outlook settings. First, the Outlook email accounts should be setup as an Exchange account and not a POP3 account. You HAVE done that, right? In mail profiles?
OK, in each Outlook client (each individual computer), you should see a set of folders for "deleted items", "inbox", "sent items" and so forth that are under the server heading "mailbox" (or whatever it's called). If you've also opened a local PST file (Outlook data file), which is only stored locally and not on the server, there should be another set of identical folders listed under "Personal Folders" below the first group. Outlook can be configured to apply "rules" to all inbound email which can move each email from the "Mailbox" group of folders stored ON the server to a folder in the "Personal Folders" group (PST file) and delete it from the server. Any email that is not stored on the server (ie: moved to the Personal Folders) can not be seen using OWA. It's even possible each person using Outlook is moving the email down to the PST folders instead of leaving them on the server, but that's another problem. :-o
To check message rules in Outlook 2003, click Tools -> Rules and Alerts. If any rules are listed there and they existed before you switched to the Exchange Server, they would still be trying to apply themselves as email arrives, moving each email to a particular folder in the Personal Folders group. Look through each one listed and see if anything appears to be moving mail. Delete any you find.
Personally, I would remove all rules you find on each client until you get this straightened out. But, if the Exchange support team chimes in soon, there may be another solution. Let's see what they have to say.