Different category behavior in GUI vs. AppleScript
I had the exact same issue. I was able to resolve by applying the exact category id I wanted like:

set end of theList to category id 33


Rather than like:

set end of theList to category "Category1"


Here is how I got the category ids. I selected a message in Outlook that had only the category I wanted and then ran this script manually from Script Editor:

tell application "Microsoft Outlook"

    set msgSet to current messages
    if msgSet = {} then
        error "No messages selected. Select at least one message."
        error -128
    end if

    repeat with aMessage in msgSet
        set theList to categories of aMessage
        return theList
    end repeat

end tell


I then used the returned category id in the code below to set messages to this category in the future (I cobbled this together from many sources online over time, so unfortunately it's not easy for me to give credit to the right folks):

tell application "Microsoft Outlook"

    -- Workaround for Outlook 2016 Reminders window bug, part 1
    set windowClosed to false
    if "Reminder" is in (name of the front window) then
        set windowClosed to true
        close front window
    end if

    set msgSet to current messages
    if msgSet = {} then
        error "No messages selected. Select at least one message."
        error -128
    end if

    repeat with aMessage in msgSet          
        set theList to categories of aMessage
        set end of theList to category id 33 -- CHANGE THIS TO THE CATEGORY ID RETURNED IN THE PREVIOUS SCRIPT
        set categories of aMessage to theList
    end repeat

    -- Workaround for Outlook 2016 Reminders window bug, part 2
    if windowClosed is true then
        tell application "System Events" to keystroke "9" using command down
    end if

end tell


I hope that helps someone else looking for a solution to adding a category to selected Outlook emails with AppleScript.

A great improvement would be removing the first manual step of getting the desired category id, and instead allowing setting category via the textual name of the category, looping through all existing categories in Outlook until you find it, and then applying that id to the selected emails. I'd be grateful if anyone improved my version this way and shared it.