MS Graph ErrorItemNotFound on some message IDs

Question

I have an Outlook plugin where users can journalize mails into an my application. The message id and some other info is sent to a service.

But there is a weird issue, only some of my users have - where some of the IDs result in ErrorItemNotFound: The specified object was not found in the store., The store ID provided isn't an ID of an item.

The id is taken straight from the mail in outlook, so i know the ID exists.

At first i thought the issue was the users had a shared mailbox and they tried to journalize from there, but adding Mail.Read.Shared had no effect.

The permission i have active in Azure is:

• Calendars.Read
• Calendars.ReadWrite
• Mail.Read
• Mail.Read.Shared
• Mail.ReadBasic.Shared
• Mail.Send
• User.Read
• User.Read.All

I had no luck in fixing this - does anyone have an idea what it can be?