I worked on search at Google around that timeframe, and it definitely used an index. As far as I know, it has from the very beginning.

You can solve the ordered list of words problem in ways that are more efficient than grepping over the entire internet (e.g. bigrams, storing position information in the index).