Let’s say ads will always make more money (I have no reason to believe they won’t), and that’s required to be the dominant search engine because the web is big and expensive to organize.

I’d bet there’s some way to characterize what I and others liked about the earlier web and create a search engine that just worries about that stuff. I’d pay $9/mo for whatever 1/3 of Google’s spend per user would get me. That’s not to say this thing would “beat” Google, but it could profitably exist.

I doubt it, because 1/3 of Google's spend per user isn't enough when you can't attract many paying users in the first place, because you would charge much more than $9/mo, because almost no one wants to pay for a search engine so your revenue will have to make up for those people too, and then even fewer people are willing to pay more than $9/mo for 1/3 of the quality.

And then I'd guess the 20 remaining users will still complain because 1999 Google is a nostalgic memory impossible to recreate without a 1999 internet for a 1999 self to live in and has little to do with raw search quality.