I'm not so sure it applied back then. Before Google, the core issue was to get a good result in the random garbage you were returned in search results. You'd use quotes and plus/minus or AND/OR operators, maybe strip out words like xxx and porn and warez, and hope for the best. Staleness was, frankly, of little concern if you got a few relevant results. That the AV index was stale was news to me before I read this thread, and I'm not sure I'd buy into the idea that it made much difference. Search engine toolbars made getting results more convenient. But the core of the problem then was getting any relevant results to begin with. For that, Google just rocked.
It did apply, to a point. Before Google, I had switched to AllTheWeb as my search engine of choice since a lot of sites just wouldn't show up in AltaVista no matter what you searched for, and ATW had a bigger index (I guess staleness could have had the same result).
But of course eventually I switched to Google for the better search results.
