I support where you're trying to go with your argument. I personally don't believe that Google is doing any of the things that are claimed by Everyman, but I think there are some problems with what you're saying:
The cookie could very well be used to track all searches. By storing a unique user ID and saving this and a search in a database, you can easily associate any number of searches to a particular computer. It's nothing the end-user would know about since it all happens on the server-side.
Sure there is. You can even do it through simple query string parameters. I've done it and I'm sure there are many webmasters who have done the same.
You pass this off as totally impossible. I don't believe Google is actually doing it, but the value of such information is quite high.
Why Google? Because they're the biggest. I think that's what this whole thread is about - Google is big, so let's target them. Of course, part of the thing is too, that because they're so big, they're the most capable of getting a valuable picture of the state of users on the web. If you did believe in these conspiracies, Google would be your prime suspect too.
Think of search information as web logs. You can't be sure that every hit or path from the same computer relates to the same user, but you can still get a VERY good picture about what's going on in a website. Plus, though the information may seem unrelated to the layman's eye, web logs can be used to derive tons of valuable information. Tracking user information is not only valuable to marketers, but it can be potentially valuable to a governing body.
But again - I don't believe it's actually happening.