Don't know about Donny, but my Outlook has the same issue. It seems to be related to importing a PST from Windows Outlook. Upon doing so, the categories list for any folder in the "On My Computer" contains any category I ever used in my old Windows Outlook
configuration, including many old categories I no longer use and no email is tagged with in the PST archive.
No matter if I'm in "On My Computer" or the Exchange server when I click "Edit Categories" I get only the category list for the Exchange server. As a result, I'm unable to delete any of the defunct categories from the "On My Computer" list, nor get Outlook
to realize that categories common between Exchange and "On My Computer" should be treated as the same category--for instance I wind up with two versions of "High Priority" -- one for Exchange (named "High Priority (<Exchange server's name>)", and one with
a different color named "High Priority" for any email in the "On My Computer" section.
This also impacts searches: since most of Outlook doesn't seem to recognize the categories in "On My Computer" exist, they do not appear in the category search field--I cannot search for anything "High Priority" in "On My Computer"--as Outlook will only
let me search for "High Priority (<exchange server>)", which is treated as a different category. The best I can do is search for "Category Exists" and then scroll through to find all "High Priority" mail.
Is there any way to synchronize the two sets of categories?