That's a good question, and something I've spent much time on. Cuil (2008-2010) tried. I knew some of those people. It cost them about $30 million to launch a full scale search engine. They had no revenue model. In retrospect, they were hoping to be acquired by somebody. It was some ex-Google people, trying to replicate older Google technology. They had a great launch, but the system wasn't very good and traffic rapi…
Also, it seems to me that both weaknesses described, legitimacy and provenance, are actually good for Gs core ad business, because if legitimate advertisers could reliably rank highly without paying, they'd have no interest to pay to out rank the competition. The competition who are buoyed by the nebulous practices Google pretends to frown upon, but for the sake of a delicate balance cannot justify completely stamping out.
The perhaps unpalatable and unutterable truth is that ad-supported search is a delicate business: be good enough to attract eyeballs, but not so good that advertisers who could pay you have no need to pay.