The solution for most of these sorts of things is just to refresh the data more quickly. Lots of queries, particularly head queries, are pretty stable in their characteristics over time. For a system that isn't absolutely critical to getting the query correct it's perniciously seductive to think that you can just push out the data once, then refresh it every quarter or so.
We used to have a problem with spelling where some news event would make a person with an uncommon name famous, but google would mistakenly correct it to a more common but incorrect name just because the spelling system hadn't ever seen this person's name before. We've fixed that issue and many other freshness related things: http://googleblog.blogspot.com/2011/11/giving-you-fresher-mo... but this is an ongoing area of focus throughout a lot of our systems.
It's an interesting problem because for many things recomputing the data faster will only fix a handful of queries, so from a raw impact standpoint hardly seems worth it. However those queries end up being ones that are in the news and related to things that people care a lot about.