Josh, when you say that Vista's start menu is totally independen of WDS, do you mean that it has its own indexer? (Sorry, I don't use vista...) [edit : removed the first useless part of the sentence)
BTW, i've never found XP's indexer reliable (Vista is obviously a different beast with its tight integration of Windows Desktop Search). So, in XP, at least, I find the Locate32-farr combination (+X1/Archivarius for deeper search) a pretty handy thing to have.
A year agp I’ve also tested Windows Desktop Search against X1, Copernic, YDS and Archivarius and it was definitely less accurate, slower and offered less features. It might have improved though (especially in Vista)! It’S been a year… Have you extensively compared Vista’s search capabilities (in terms of accuracy, speed, features…) to other solutions?