Ive seen this on rare occasion and it seems like i had to create a new .pst(mailboxfile). Sometimes the file gets corrupted especially if they get over a certain size but its usually over 1 gig or more. If your users store their info in .pst or .ost files check them. I would back those files up and redo their email to make sure its clean. Just make sure you get all of the files from their profile folder. This may not be your exact situation but its what i did and worked for mine. You shouldnt have to reload outlook just the accounts. Remove them and add them back. If it doesnt work then you might try a full reload.
Sometimes when those files are saved several times with those odd errors and the repair tool doesnt catch them. Also you might see if there are other odd problems going on with the system. It may be the users full profile folder e.g.:(W2K) \Documents and Settings\\. I had one instance where the profile was corupted and was causing odd problems with office.Backup any possible data and remove the users profile(done under admin). YOu can right click my computer select properties and should be able to locate user profiles there.
Hope this helps to shed more light
Jason
