However, focusing on my suggestion of transparency and verification misses the point. The method by which Google regains (and maintains) the public trust is their problem, and I'm sure that more than one solution exists.
My point is it would probably be in Google's best interest to fix this problem, because waiting too long has consequences. At some point, the people who feel that are treated unfairly by Google - it doesn't matter if they are correct in that belief - will fight back, which has already started in small, preliminary ways.
> The outcome would be ugly.
The outcome would also be ugly in a future where a socially-necessary service is controlled entirely by a single entity. As usual in these situations, the best situation is somewhere in the middle.
To your broader point, I agree that it's reasonable to want Google regulated to some degree, though I do fear regulators will take on that "transparent algorithm" point of view, which will just make search terrible. Governments generally aren't very good at regulating tech businesses.