I had those problems several times. Perhaps this article can help to solve it: Outlook Search. I finally gave up and changed my search software to Lookeen and it is running without problems.