I don't know the exact answer - perhaps no one outside of Google knows. But I have two data points which may be useful.
The first is XKCD's take on the issue:
So it really looks like there’s a certain threshold of result volume beyond which Google apparently says “screw it” and throws out a gigantic number. I imagine this is probably due to incompetence rather than intentional deception; I’m sure it’s hard to generate pages quickly from many sources, and maybe for searches with a lot of results they don’t have time to get it all synced up. So they fudge the numbers. The fact that this makes it look like they have way more results than they do is presumably just an unintended bonus.
The second data point is from a computer science professor I had who was quite curious about the issue and bothered some friends at Google about it. They told him that sometimes it becomes very expensive to figure out how many results were really returned from a search, so they just make a best guess and return the first page of results, which is all most people care about. Only when you actually start drilling down through the pages does Google bother to fully calculate the remaining pages.
So neither of these is a definitive answer, but hopefully they will be useful at explaining the kinds of issues that may be causing Google's inaccuracies.
Sathya's answer on this page has an answer from Google's Webmaster KB.
When you perform a search, the results
are often displayed with the
information: Results 1 - 10 of about
Google's calculation of the total
number of search results is an
estimate. We understand that a
ballpark figure is valuable, and by
providing an estimate rather than an
exact account, we can return quality
search results faster.
In addition, when you click on the
next page of search results, the total
number of search results can change.
In this case, we realize that some of
the query results are duplicates, and
collapse those duplicates so that you
can find the specific result you're
looking for more easily. Collapsing
the duplicates decreases the estimated
number of results, as well as the
overall number of results pages.