Try Disabling and Enabling it. Control Panel - Programs and Features - Turn Windows features on or off. Select Windows Search. Disable, restart. Enable, restart.
Next Right Click anywhere on Start Menu (not the bar) and select Properties. Click Customize and chose your Preference under "Search other files and libraries".
Then try installing Everything if the above doesn't help.
You may also find these helpful: SFC Scan Repair Install Disk Check