Hard to say what the problem is, but the search is case sensitive so using the example the subject would have to contain e.g. [CAT1]

If you make changes to the code, you would need to run Application_Startup again

If you want to run the process on mails you send then in the ThisOutlookSession module add the following. This is a built-in event so doesn't rely on the Application_Startup macro to work.

Private Sub Application_ItemSend(ByVal olItem As Object, Cancel As Boolean)
    With olItem
        If InStr(1, olItem.Subject, "[CAT1]", vbTextCompare) > 0 Then
            olItem.Categories = "CAT1"
            olItem.Save
        ElseIf InStr(1, olItem.Subject, "[CAT2]", vbTextCompare) > 0 Then
            olItem.Categories = "CAT2"
            olItem.Save
        ElseIf InStr(1, olItem.Subject, "[CAT3]", vbTextCompare) > 0 Then
            olItem.Categories = "CAT3"
            olItem.Save
        End If
    End With
lbl_Exit:
    Exit Sub
End Sub