@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.