inkybuck : Ok, that is obviously more complex than I thought :-), and I agree that a certificate would not help here at all.
I didn't read the news as the OAuth login for ExO's PS module would go away, though. From all I see right now, I get the impression that MS at some point might want to replace all those dedicated PS modules with the Graph SDK, but I guess they are still very far from that goal, if it actually is one.
I get what you want to achieve with your product, and I understand the idea is to make it as comfortable as possible for your customers, but I can tell you from the point of view of a rather skeptical admin: I would never enter my internal credentials into a vendor's product for the approach that the system does some "blackbox magic" to set itself up. I would always want to know exactly what's happening there and very much prefer a checklist and a manual on how to do this setup on my own, so I really know what the system is doing in my environment. Maybe that's just me.. ;-).
The general MS approach to that I think would be that you create an Azure app with the needed permissions that customers can setup from the gallery, and once they have granted the access in their tenant, your app can do its thing. Unfortunately I think it is not possible currently to only acquire certain permissions for setup and remove them later on, at least not in an easy way. But I don't know enough about this topic to really be of help here.