When you logged onto another computer using the problem users credentials, did you have to create a new Outlook profile, or did one already exist?
If yes, then time to dismount and repair the mail-store.
If no, then it could be a corrupt profile / .OST file in which case, delete the profile / .OST file and re-create.