Some people do use Bing. The reason more people don't is that there isn't a lot of reason to. Even if you can get the results to be as good as Google, actually making them better is hard. And it's just trading one giant tech company with privacy issues for another, so that's no advantage either. People need a reason to switch away from the incumbent.
But if you fund the development as public domain research and open source code, that's a different story. Now you're putting it within the capacity of even medium sized organizations to do their own indexing and run their own search with quality results. Instead of two competitors, you open it up to potentially hundreds or thousands.
If the Wikimedia Foundation or similar started doing search indexing, people might actually trust them more on privacy than they do Microsoft or Google.
And the more of them there are, each running their own fork of the code, the harder it is for SEO spammers to pollute the results, and the more advantage the little guys have over an incumbent that spammers will still continue to specifically target as long as they continue to have high market share.
If the code was available for anyone to adopt or modify, you could also get some potentially interesting new domain-specific search engines. There isn't a lot of high quality competition in the video search space, for example, and if there was then that would help to erode the dominance of YouTube by making videos hosted elsewhere more findable.
You would also be likely to see it displacing Google Custom Search pretty quickly if it was free to adopt.
And what's the cost? An amount of money less than they've received from Google in fines? The worst case is that it only helps a little instead of a lot. (And it wouldn't hurt to do the same thing against Windows considering what Windows 10 is doing on the privacy front.)
What you propose actually sounds like it could be a better way than the status quo (privacy issues or not with current providers), and if it fails, you can always go back to hitting up the rich uncles for ransom!
Even if they were to regulate beforehand, any company they would allow could evolve slowly into something that breaks the initial idea of what was allowed.
Legal systems are like code, except interpreted by humans and “common sense” instead of compilers — we just don’t have a way to make it simultaneously easy to understand (legalese), hacker-proof (legal loopholes), and future-proof (implications of new tech).
Governments do try to clear out old laws and amend the ones they want to keep, but it looks like it’s as hard for them as preventing databases from leaking is for us.
I think of the Internet as a public utility. I think it needs to be regulated as such.