I have seen outlook profiles be come corrupt for various reasons.....usually due to size of the mailbox.
Seeing you mentioned pst files...I am assuming Outlook...not Outlook Express here
What is the server Outlook is connecting to...is it just a POP or an Exchange etc?
Check the filters and views the user has setup...I have had a user filter her mail and all of a sudden mail wasnt "there"....and once I reset the views to default and removed the filters...voila..the mail was there...sounds like this may be the issue.
Outlook 2003 has has many an update to the junk mail filters........make sure you are up to date on the patches.
Really sounds like a view thing to me though
Or you can try creating the users profile on another machine.....see if it works there?
Or....... create a new outlook profile on the machine
From Outlook I export the mailbox to a pst file at the root of C:\ and call it backup.pst
(include all sub folders...this is VERY important)
I then delete the profile and look for the users pst file...usually in the users profile\documents and settings folder......(really depends on the version of outlook and windows) and delete that pst file.... a search for *.pst will usually finds the other pst file....sorry cant remember where it is stored right now...do not delete the backup.pst you just created at C:\
I believe pst files are considered hidden\system...so you may want to adjust your search to include those
I then recreate the profile in outlook and import the backup pst ...unless of course I am connecting to an exchange server...I should not need the backup.pst as the mailbox really resides there..just needs to synchronize....backup.pst is there....just in case..all else fails
A new profile has fixed outlook many times for me.....
Again..what version of outlook...and what server??