The problem is almost certainly that its local cache is corrupt… which happens disturbingly frequently. The easiest way to fix it is to simply close Outlook, delete the local cache, then start Outlook again – the good news being that it works and your new mail starts showing up; the bad news being, of course, that it starts synchronizing /everything/ again.
Stick this command in a batch file, and you’ll have something that users can simply double-click to fix the issue. Just remember to tell them to CLOSE OUTLOOK FIRST! =)
del "%UserProfile%\Local Settings\Application Data\Microsoft\Outlook\*IMAP*-0*.pst"
