@davewill: Given that unique ID, is there a way to track back to you? I doubt it.

A search query probably looks like this:

Phone: I want to do a search. My ID is 1234, and my query is "find me pizza near 5th street"

That's only conjecture based on the privacy statement, but from the server's point of view, 1234 is just a number and there's nothing to tie it to a person. If they were caching more than that, it would be a problem. However, that would mean that their privacy statement was dishonest, which is highly unlikely.