Issues with Single-Sign On for Federated IDs

About two months ago, we started having problems with SSO for some of our Federated IDs.

When users are requested to logon, the Adobe CC Cloud Desktop will redirect them to Microsoft Edge for logon. The user then enters his e-mail address and the authentication towards AzureAD runs and sends the user back to the Adobe page. Instead of a successful logon, we get for a rising number of users the message "Something went wrong. Please wait as we work to fix this problem, then try again. If the problem persists, contact customer service".

According to the logs on Azure, the login is successful, so the problem must be somewhere on Adobe's side.

The problem just started with existing users also. But not all users (old or new) seem to have it

If the user starts the logon process from within the Adobe CC Cloud Desktop App, they will be asked for e-mail, then password and finally for their second factor, if the user has been setup for Multifactor authentication. And if the user is activated for MFA, the logon is successful and the user can start using Adobe CC.

Hopefully someone has an idea... I will also start contacting Adobe customer service and report back here.