It's strange that the problem persists with both Windows 7 and XP.
You could try using the 'Inbox Repair Tool':
How to find and run the Inbox Repair tool in Outlook
In the above link there is a Microsoft 'Fix-it' you could use.
This appears to be over my head. I will see if IT can spend a few minutes figuring this one out. Thanks.
I asked IT and this is what they've said, "It has already been tried... I am going to upgrade his machine to Windows 7. This means I will back up the entire machine, install a fresh copy of Windows and Office 2010 and see if the problem gets resolved."
Let's cross our fingers!
Now, he already told me, though, that he tried it in Windows 7, so I don't know how this will actually fix it, but let's hope.
Quote