Turn this on, the log might point you somewhere:
File > Options > Advanced > Other > Enable troubleshooting logging
Have a look in…
File > Options > Search
…at following:
1. Results
Change radio button to 'All mailboxes';
Untick 'Improve search speed…'
Tick the bottom 'Notify me'
2. Sources, 'Indexing Options…' button
There's a bunch of useful-looking stuff there which might help.
|