SaschaSeipp We actually already use the Graph API for some things, but unfortunately it doesn't do everything we need, some things are only possible through PowerShell. (There are also things that are only possible through graph, which is why we use both.)
What prevents us from using a certificate is that it's not really suitable to our scenario. We make a product that scans email for phishing and other things. We need to add connectors, transport rules, and other configuration to the customer's Exchange Online tenant so that it will send the mail to us to be checked, and accept it back afterward. To do this, we have a web site that, originally, got the user's email address and password and used them to log into PowerShell, then made the necessary changes to their tenant. Now, it uses OAuth to get a token that can be used to log into PowerShell - but this is an undocumented method that I imagine my go away, since it sounds like the EXO PowerShell module is not using that method anymore.
The certificate method is unsuitable for two main reasons: First, using a certificate would mean that instead of just having the customer log in to our site with their Microsoft credentials, they would have to go to the Azure AD portal and set up the certificate, which would be rather more complicated especially for non-technical customers. Even if they can do it, it would create a huge amount more friction than just needing to log in, and would be a terrible customer experience compared to what we have now. Second, that would grant us the ability to log into PowerShell for their tenant permanently (unless and until they go remove the certificate setup from Azure AD). We don't want that, we just want to log into PowerShell for them this one time and do the setup needed for our product, and when we log out, not have any ability to log in again by ourselves (and therefore not have to protect a token or certificate that would let someone do that).
The certificate is great for the scenario it was intended for, running an unattended script. But that's not what we're doing. We want to interactively get a delegated permission to use PowerShell on a customer's tenant on their behalf.