Hi @Varun Goswami ,
What's the version of your Outlook desktop client(File>office account>About Outlook)?
Are you working with "show as conversation" like below?
According to my tests, if you work with conversation view and category the first message, all messages later in this conversation would be categorized automatically, which may cause your issue.
If it's your case, as an alternative, it's recommended to double-click the specific messages and category it there like below, or you could turn off "show as conversation" before you category it.
Hope that would be helpful to you.
If the response is helpful, please click "Accept Answer" and upvote it.
Note: Please follow the steps in our documentation to enable e-mail notifications if you want to receive the related email notification for this thread.