One of the solutions involve natural language queries (yey!) - but it's a "complete mess" at the moment, being ambiguous, domain specific, etc...BUT he did find, as I did, and Jimmy Lin did, that users preferred natural language querying.
During the Google Ninja challenge I set you all, I have found that the majority of people are indeed using natural language in Google, and I think this is because of the complexity of the search context. Watch this space.