If the index isn't updated instantly then they should account for that by first searching the index (for speed) and then manually trawling through the Start Menu folders for results which are missing from the index.