I imagine they'd still make their revenue from advertising - they'd have an adsense bar. This would put the search part of the business on the same footing as other sites selling advertising space.

I'm imagining a world where there are multiple adsenses (ad brokers) competing effectively with each other for space, driving out supernormal profit for brokers, and returning the bulk of the advertising revenues to the publishers rather than to the middleman (currently Google). With more revenue for the publishers, more publishers come online and drive out supernormal profits for publisher too. That would be a more efficient market.