Strange: Users can't delete items from public folders in Outlook 2016 when the client has been logged in for about 30 minutes

We are running Exchange Online and Exchange 2013 in hybrid mode. Our public folders are hosted online. After a fresh boot/reboot, our users can delete items (permissions vary from Owner to PublishingEditor), but:

• After about 30 minutes Outlook tells them that they don't have the permissions to do so.
• If they check the properties of the folder in their Outlook clients, it will show the correct permissions
  • They can still delete items in those folders from OWA

So it seems to be a client problem. We already tried re-installing Office on some clients. The caching for public folders is turned off. I don't really know what else to check...any ideas?

EDIT: The Eventlog gives me 300756 and 0x80004005 as error codes in OAlerts (Microsoft Office Alerts)

How many on-pre users run into the issue, all or the specific ones?

Have you configured public folders for in Exchange online with the process in the below link? If not, please have a try, especially the step 3:

https://docs.microsoft.com/en-us/exchange/collaboration-exo/public-folders/set-up-modern-hybrid-public-folders

Does it also error in Outlook safe mode? To open Outlook in Safe mode: Close Outlook then hold Ctrl as you click on the Outlook icon. You'll get a message asking if you want to start in Safe mode. Click Ok.