I found an answer that completely resolved these issues for me. And it made complete sense once I discovered it. I do not use SkyDrive - But in my Windows 8.1 installation, I had noticed that opening the file explorer defaulted to SkyDrive.
In the Registry; sub values in the entry HKEY_LOCAL_MACHINE\SOFTWARE|Microsoft\Windows Search\FileChangeClientConfigs pointed to SkyDrive. (I suggest that you verify this on your systems prior to proceeding)
I renamed HKEY_LOCAL_MACHINE\SOFTWARE|Microsoft\Windows Search\FileChangeClientConfigs so that if needed I could restore it. Then I restarted my PC.
Search issues with both file explorer and Outlook search issues were fully resolved after reboot.
I have seen several problems introduced by Microsoft implementation of SkyDrive. My next problem to work is to completely remove SkyDrive with "breaking" things. Have not found a way yet.
This one did it for me, thx!
Just deleted the subvalue, and everything is working.
Other symptom was not being able to launch indexing options from control panel at all.