I recently found that nothing was indexing so I couldn't use Instant Search. This was very annoying and I was very confused! It turned out that I'd changed my power options for Search to "Power Saver" as I thought "well, I don't use search in Windows [idiotically forgetting Outlook!] so I might as well stop it indexing the majority of the time" (I'm well aware there other ways of reducing the impact of indexing, I was just fiddling around at the time). Well, I forgot that I'd done this, of course, so I was stumped for a while (didn't solve it and didn't spend that long trying). I finally worked it out just now so thought I'd share this bit of information … having said that, there's probably no-one stupid enough to have done that anyway but you never know!
If this isn't your problem then double check that you have configured the Indexing Options correctly in Control Panel. Otherwise, back to Google you go.
Hope this might help another idiot out there! 
georgebonney