AD Guest Users unable to access SharePoint Online

We have:

• M365 with SharePoint Online
• A communication site set up in SharePoint Online
• A bunch of about 300 guest users from other companies

The Problem:

• A certain fraction of the guests from other companies cannot access the SharePoint. They always get the „You need permission to access this site“ form. They can fill it out, our admins get the request, grant access, but still the users see the „You need permission to access this site“ site.

What we did to debug:

• We worked through this guide: https://learn.microsoft.com/en-us/sharepoint/troubleshoot/administration/sharepoint-online-inaccessible
• We worked through the „"Access Denied" or "You need permission" errors in SharePoint Online and OneDrive“ guide: https://learn.microsoft.com/en-us/sharepoint/troubleshoot/administration/access-denied-or-need-permission-error-sharepoint-online-or-onedrive-for-business
• Especially we run through the „Check User Access diagnostic“ tool in the Admin center. For all users affected, it tells us, that appropriate rights are given and the users should be able to access the site.
• We checked our own AD as well as ADs of the companies we invited the users from if there seems to be anything strange. Nothing seems suspicious.
• We deleted and re-invited guest users in our AD. Nothing changes even with a new user id.
• We assured, that we are not hitting any threshold, i.e. that after a certain amount of guests new guests get blocked. We still see single n+1 Users, that can access.

Some more information:

• It seems quite random, which users are affected. We could reproduce with at least one user from each tentant we invited guests from, while at the same time we have users from each tentant that can access without problems.
• It does not seem to relate with our communication site in Sharepoint, its access to our SharePoint in general, that is blocked.

Any help appreciated!