I have the cause now, which is one or more Outlook add-ins, and the
fix. I opened a case with Microsoft finally, who said a number of
customers have called in with this same problem.

Here are the steps they had me do to prove the cause:
- Make sure 'Use Cached Exchange Mode' is checked
- Close Outlook
- Open Outlook in safe mode (Start, Run, Outlook /safe)
- Try to categorize an email in the shared mailbox--it worked
- In Outlook, Tools, Trust Center
- Add-Ins
- Manage Exchange Client Extensions, Go
- In Safe Mode, these are all unchecked, but in regular mode they're
checked

Then they had me disable add-ins by renaming the add-in registry keys:
- Close Outlook
- Start, Run, regedit
- Go to each of the following registry keys and if you find an Addins
key then rename it to OldAddins
HKCU/Software/Microsoft/Office/Outlook/12.0
HKCU/Software/Microsoft/Office/Outlook
HKCU/Software/Microsoft/Office
HKLM/Software/Microsoft/Office/Outlook/12.0
HKLM/Software/Microsoft/Office/Outlook
HKLM/Software/Microsoft/Office
- Open Outlook normally (not in safe mode) and it again worked fine

Microsoft says that the problem is one or more of these add-ins
causing the problem. Add-ins are what 3rd parties write to interface
with Outlook.

So, they said you have several options to fix it.
1. You can leave the add-ins disabled permanently. These add-ins for
Outlook won't work and your users may complain or not notice,
depending on if they use the functionality provided by the add-ins. In
my opinion this is not a desirable fix, especially if your antivirus
add-in is disabled.
2. You can try to figure out which add-in is causing the problem.
Here's how:
- Back out all the changes you just made to Outlook by closing Outlook
and then renaming the OldAddIns registry keys back to AddIns
- Open Outlook normally
- Go to Tools, Trust Center, Add-Ins, Manage Exchange Client
Extensions, Go
- Systematically uncheck one option at a time, restart Outlook and see
when the categorize problem stops. Or uncheck all the add-ins and then
systematically check each add-in to see when the categorize problem
starts.
- When you've identified the offending add-in, see if there is a newer
version of that product available and upgrade to that product. For
example, if you discover that Symantec Antivirus 10.0 is problematic,
see if Symantec has released AntiVirus version 10.1 or newer.