It doesn't necessarily have to be a direct payment. Companies can white-label the service or include it as a value-add as part of their offering; for example an ISP or mobile carrier offering this to their customers.

At the moment I'm not aware of any company whose primary service is search. I believe the demand would be there - OS manufacturers currently have to either put up with Google (even if their goals diverge - for example it doesn't work well with Apple's privacy-focused marketing) or Bing.

A third player whose primary business is search (as opposed to using it as a loss-leader to lure people into their ecosystems, like Google and Bing are) could get some use, not to mention that programmatic access to large web index would no doubt be a service many companies would pay for. Think Algolia or hosted ElasticSearch but pre-seeded with a broad index of the web.

It doesn't have to appeal to every internet user. Not even most internet users. It just has to appeal to enough to make money, which is a substantially smaller number than the total number of internet users.