The issue only occurs in very specific situations.
When no other connection to Office apps has been made already (Teams, Outlook, Sharepoint, OneDrive, ...) and one tries to connect to https://portal.office.com (e.g. using the "Office Online" icon on desktop, you can get the error.
Our Home page connects to Sharepoint, so when a browser is opened first, our users do not get the error, but when no browser is open yet (and no other connection to Office Apps is active), when users try to connect to "Office Online" they seem to get the error.
We managed to find a workaround on this issue, normally when browsing to https://portal.office.com, after providing credentials, the landing page is https://www.microsoft365.com/?auth=2. When changing the URL behind the "Office Online" icon to this URL, our users do not get the error.
Looks like something has changed at Microsoft with the signon process on the "portal.office.com" website (as previous comments also have stated)