From Google's privacy page [google.com]:
Is this a misprint? No. I've given Google plenty of opportunity to deny that they record IP address with each query, and they haven't denied it. Notice that they say, "notes and saves ... with each query." That means they record it and store it. They also record and store your unique cookie ID and your search terms with each query.
I fail to understand how intelligent people can read it right on Google's site and then insist that Google would never do such a thing. The only thing that comes to mind is the notion that there's a "Google cult" out there that could use a bit of deprogramming.