You already trust your search engine to rank results based on your search terms. They can do the same thing for their ads without having to do additional tracking. These features can pretty easily be added to the auction if you consider bad ads as a cost to your company.

You end up showing the ad that maximizes something like bid * click_rate + quality_score * quality_value. quality_value can be tweaked to change the balance between short-term revenue and ad quality.