Windows Indexing Service was bundled by default with Windows 2000 and integrated in search interface (it was available before as option for NT 4.0).

The main difference is that it was way less known, and early on it required considerable time to process things because of less powerful computers being norm.

All right, valid point.

It was intended for indexing IIS websites, although by W2K it could handle MS Office files. Was it directly visible from Explorer? The first Windows I personally remember with file search in the desktop – for instance, in the Start menu – was Vista, which came out in 2006 and which has a totally different indexing and search tool which replaced Indexing Service.

Yes, the default windows search boxes utilized indexing service if it was enabled. Windows 2000 also shipped with a ton of IFilter modules to enable indexing of various files. It was also first shipped for indexing IIS, but originally was part of Cairo as whole-OS indexer.

Vista introduced "next generation" implementation and used it by default, though you could still use the old one. IFilter remained the same for both. What really changed was how it was more visible and less performance impacting with newer computers - most people I knew disabled indexing because performance and there was no real culture of using built-in windows search.