I distinctly remember that my typical workflow involved searching on AltaVista plus another search engine. The advantage AltaVista always seemed to have was that it had a larger index than a lot of competitors. Often, the ranking was not especially good for obscure topics, so I remember I would often have to dig into 2 or 3 pages of results to find what I wanted. When Google came along, I would search AltaVista and Google. Google always seemed to require less digging that AltaVista.