My new notebook had some sporadic slowdowns during the startup phase.
Looking into Event logs, I found several Event 3006, 3007, 10021 all around Windows Search engine.
After some searches on internet, I found this page.
Those guys had the same problem, and the solution seems to reinstall Search Engine feature.
Into Windows 8.1, this is not so easy, because it disappeared from the Control Panel ‘Features’ window.
Thankfully, it can be done by command line too.
The first step is to open an administrative Command Prompt window.
To uninstall, type the following:
dism.exe /online /Disable-Feature /FeatureName:SearchEngine-Client-Package
Reboot, and open another Command Prompt window, and reinstall it by typing the following:
dism.exe /online /Enable-Feature /FeatureName:SearchEngine-Client-Package