Search engines are key to finding information on the web. Search presently is free for users financed by targeted advertisement. Today, the current search terms determine the ad placement. In the near future, search-engine providers will make use of detailed user profiles for better ad placement. This puts user privacy at risk. Anonymizing search histories, which is a solution in principle, gives way to a trade-off between privacy and the usability of the data for ad placement. This paper studies this tradeoff systematically. To this end, we implement an algorithm for the anonymization of search histories which is flexible regarding the target function. It can retain frequent terms or terms where corresponding ads are clicked with a high probability, keep up the number of users it can derive interests for, etc. We quantify the usefulness of the anonymized log for ad placement in a broad way, e.g., by estimating the number of ad clicks or of ad impressions, based on marketing data from Yahoo! As a result, anonymized search logs are still useful for ad placement, but this very much depends on the target function.