From John Battelle’s Searchblog:
1) “Given a list of search terms, can Google produce a list of people who searched for that term, identified by IP address and/or Google cookie value?”
2) “Given an IP address or Google cookie value, can Google produce a list of the terms searched by the user of that IP address or cookie value?”
I put these to Google. To its credit, it rapidly replied that the answer in both cases is “yes.”