I would not be surprised if google still has the data. Not sure how google handles things internally. However, google needs to pull up the results fast. So they might have 4 billion results with the word "water" in it. They only make tiny portion of that available. So if I type the words "Hot water" google it looks at the subset of pages with words "Hot" and the word "Water" So google must pull the pages that have both words quickly. So the number pages in these subsets "Water" and "Hot" must be small enough to quickly be merged/intersected. There are other things that could be done to speed it up, but I think you get the main idea.
However, what I am getting at with that simple example is for the searches to be quick google keeps these lists small. So there is a limited space due to time-constraints. So google must decide what is relevant for the available portion of their index.
However, that does not explain why other search engines don't have trouble with older sites/links. I suspect it's more of business decision than a technical one.