I don't think such regulation should be restricted to AI. "Google-style B2C blanket bans" routinely ruin people's livelihoods in other ways, including, of course, when Google does it. There are way too many companies nowadays that are way too central to how way too many people live their lives.

If you want to be a piece of critical infrastructure, you need to deal with the implications of that. It's not OK for private entities to be able to "unperson" people in important parts of their lives for what amounts to convenience reasons. If them not being able to do that raises the price of the service, so be it.

Honestly even banks, which are already highly regulated and at least have more nominal competition, still have too much leeway to cut off customers based on error-prone statistical methods, without recourse or explanation.