We tried Yahoo: It's a complete waste of time and money. Ads were always edited by Yahoo staff (requiring frequent e-mails to clarify the service we were paying for), bids may be changed at random, the interface is a nightmare kludge and there is no way to opt out of Yahoo's 'partner network' (which seems to consist only of spam domain landing pages), so bidding a keyword to the top of the Yahoo search results guarantees a load of expensive visitors from click-farms. I would love to advertise on Yahoo's search result pages and will do so the moment Yahoo Search Marketing is taken over by a competently run organization (Go Microsoft!).
We tried Ask.com: You'll receive a tremendous number of visitors on your first day, all from spam domain landing pages. There is no way to specify "place my ads on Ask.com search results only" (which I'd genuinely like to do), so money given directly to them is wasted. Crazily enough, you can cancel your Ask.com advertising and opt into using Google's "Search Network" instead. That will put your ads on Ask's search results without having to deal with Ask.