Create a ticket with Microsoft. Unless the severity was High or Business Critical and contacted our account managers to speed up the process, it took me a few days to regain access. The process is something like this based on my current experience:

1: Create a ticket with Microsoft. Give them the tenant ID which is locked out in your description. Tell them that no admin account has access anymore and your partners also have no access anymore. Otherwise this is the first question you will receive from Microsoft support.

2: Ticket is assigned to the Microsoft 365 Data Protection department/team. They verify if you are authorized for this request. There are a few ways to prove you are authorized.

They try to contact the configure (technical) contact by Phone. They call the phone number which is configured in your tenant information. If you pick up the phone and they are able to verify it’s you, they can proceed to the next team.
They send an e-mail to one of the Global Admins. If they respond EXACTLY what they ask within an hour the process continues to the next team. If the Global Admin did not respond they send e-mail to all users who have some administrator roles assigned. If they respond EXACTLY what they ask within an hour the process continues to the next team.
If responding to one of the above e-mails is not possible, they ask you to create a TXT record in one of the verified (custom) domain names in the tenant. The TXT record value must be the exact same date of today (for example: 09-09-2022). Microsoft verifies this by using mxtoolbox.com. If so, the procedure continues.
After completing the above steps they ask you to deliver the following legal documents. These must be uploaded to a Secure File Exchange link which you receive from Microsoft Support.

3: While being verified tons of times, they assign the case to the Azure Product Team or Office 365 Premier Support team. They ask you to do a failed logon once and send them the Request ID, Correlation ID and timestamp as shown in your failed logon details. This gives them ability to verify your Azure AD Sign-in logs and investigate the actual issue. In my case it was a Conditional Access policy.

And than there’s the moment we’re waiting for.. The ticket is finally escalated to the Azure Product Team or a Microsoft 365 engineer (Tier 3) who will unlock your tenant! In my case they excluded one verified global admin from a specific conditional access policy. I was now able to logon, regained access and immediately modified the CA policy which was causing troubles.