i had the same issue - I found that I could not find any mails using search in outlook since May. I tied rebuilding the indexes, and checked that the indexing status was "0 items to be indexed". This did not help.
Then I remembered that I installed the outlook.com connector around this time. I disabled it from the options, restated outlook, and Bingo, I now see all my mail when I search, right up to 10 seconds ago. So indexes were fine, but outlook.com connector
"broke" the search.
The outlook.com connector never worked anyway - it would recieve mails, but I could never send mails. When I tried, it poped up a captcha type dialogue, but where the image should be it always said Error getting image or similar, so could not send. As
outlook.com accounts dont support IMAP, Ive migrated away from outlook.com back to gmail.com addresses, and now outlook is happy.
Actually, not all is good. Since I disabled the connector, now all emails are appearing 2, 3 or 4 times as duplicates when I search. The duplicates are messages sent to a single address, and are all shown as being in "inbox". Even old emails from last
year are doing this. When I had the outlook connector installed, it was only showing one email (but no recent ones). some emails are also showing up in "inbox" and "all mail" (but not all of them). I set outlook to always search all accounts (I have about
5 IMAP email accounts setup and one exchange).