Graph PATCH Categories in shared mailbox

Question

I am trying to set mail categories from an Outlook AddIn, via MS Graph. When I call the PATCH for a users mailbox, this is working like a charme. Like this:

PATCH https://graph.microsoft.com/v1.0/users/{some-users-mail-address}/messages/{message-id-to-categorize}

If I use a share mailbox instead I get an error 403. I already added the permission:

Mail.ReadWrite 
Application 
Read and write mail in all mailboxes

This should be enough, right? From the description, I'd expect this to include the shared mailboxes, too.

I found there is a delegated permission Mail.ReadWrite.Shared, but I cannot use it since I am not in a context with a user and is not selectable as application permission.

Found this: Generated token is not able to access Graph APi to read shared mailbox messages Admin consent is given for all scopes.

EDIT: If I check the token as Shiva Keshav Varma suggested it prints:

"aud": "https://graph.microsoft.com",
"idtyp": "app",
"roles": [
  "Mail.ReadWrite",
  "User.ReadWrite.All",
  "Directory.Read.All",
  "User.Read.All",
  "Mail.Read",
  "MailboxSettings.ReadWrite"
],
"ver": "1.0",