with the obvious focus on increasing the user experience, and the unfortunate opposite effect you get with the new system (ie people selling laWebmasterWorlders can bid on the phrase key chains as long as they are willing to pay the money) perhaps a regular "relevance" check or something is needed, where blatantly irrelevant searches should simply be removed.
As long as the "irrelevant ads" have a higher CTRxCPC they are relevant. Why else are people clicking them?