Implement a proxy authentication scheme for the hosted services (WP, etc). Now an admin working for the hosting provider can log in using a password checked against a hash stored in their hosting system. No plaintext passwords stored.

> the hosting provider can log in using a password checked

Hmm, but where is this password stored? This sounds like exactly what they were doing!

They have access to the DB users. You can craft a new user & password-hash pair and insert it into the DB to create your own Wordpress user to manage on their behalf, or the lazy way is to just update the user’s password hash with your own. Then when you fix the issue, revert it. Worked for me years ago, not sure if something fundamental changed