From the user's perspective, it's still a pretty good deal. There's a 99.999% chance that you get to use gmail/youtube/etc for free. And a 0.001% chance that you'll end up a statistic, and need to pay a nominal fee for an appeal.
Unfortunately, I don't think the above will ever happen, because it would be a PR nightmare. "Google wants to charge you money, just to appeal a ban!" It's still better than the status quo, where people have almost no recourse when they are banned. But it still sounds way better in the media, if you just pretend as though these things never happen. Hence the status quo - use automated systems to cheaply get to a 99.999% success rate, and spend as little money as possible on the remaining 0.001%
And if companies don't want to do it, that should be easy to regulate though. Requiring a human centric appeal process even if it has a fee, and prohibiting blanket account bans (if you get banned on gmail it doesn't affect your android and play store accounts, for example)
There are other provisions that I consider important like not being able to reuse email addresses and requiring the forwarding of email for at least 6 months after any account termination (getting banned from your email address can have disastrous consequences)
The answer is to force google to be open and more transparent through regulations and have to scale up to deal with it and eat into their profits.
The assumption up front should not be that we need to care about protecting their profits.
They probably made a TON of money off of that, and off the credit protection services they offer directly or through subsidiaries.
It need not be, as long as the fee is less than the cost. It could be symbolic (say $1). But the problem is that it would be seen as a revenue generator whether it is or not.