On Windows Vista and every subsequent version of Windows, if I search for a file and include the entire C:\ drive, I might very well have time to make tea or a sandwich while the search results come in. On Windows XP, using the search dialog with the animated dog, I can search the entire C:\ drive and expect it to be done in a minute or two, if not in seconds.
It can’t just be nostalgia; I can replicate these results on period-accurate hardware today. What changed with Vista to make file searching so much slower, even with indexing enabled?
The question is basically answered now, so I’ll just drop this video here for some additional context about Microsoft’s history of trying to build a file system that solves the problem, and the challenges they faced even in the early XP days:
https://www.youtube.com/watch?v=h5d5H92c4Mk
tl;dw: MS tried to understand the context of each file, not just the name. Once you add dozens of pieces of metadata to each of tens of thousands of files (even 20+ years ago), the whole system became too difficult for them to properly index and manage efficiently.