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?
I’ve noticed this too. I’ve given up on it and instruct others to look for programs in the start menu alphabetically instead of searching because even that is bad. Same with Outlook searches, I instruct people to use webmail because the searching works there.