If a shortcut doesn't work as expected (i.e. as mentioned in the help text/manual) check whether you configured the same shortcut as global shortcut in System Preferences > Keyboard > Shortcuts. If you set up a "concurrent" shortcut it may also occur in Services, Screenshot etc.
Also check the app's preferences whether you set up custom shortcuts which ...
You can delete the category by finding its ID and using the command:
delete category id <#>
So something like this works fine:
tell application "Microsoft Outlook"
set badCategory to "foo"
set allCategories to every category
repeat with varCategory in allCategories
if name of varCategory is badCategory then