So, I had an opportunity this week with a user who didn't need an immediate fix, so I just had an opportunity to actually investigate. Unfortunately I fixed it too quickly before I learned a whole lot.
The first thing I tried was examining the mailboxes of the affected user and my own account using MFCMAPI, but I couldn't find anything obvious, so I then tried the Outlook Repair setting under Account Settings / Email Accounts, and at first that didn't seem to work. it first failed to find any server settings, and I had to log in manually. It did not appear to fix anything. I tried running it again and it immediately came up as successful and the problems were all resolved.
I don't know whether it was the first attempt at the repair tool that fixed it, or the second. But I will try this again the next time I get another user with the issue, which probably won't be long.
My big question right now however, is there anyway to automate this repair procedure? A command line I can run which would do it automatically?