Go back into Services.msc and change Windows Search startup type: back to Automatic (Delayed Start)
then START the service.
Copy the next line:
msdt.exe -ep SystemSettings_Troubleshoot_L2 -id SearchDiagnostic
(Highlight the line then Ctrl + c)
It should find Command Prompt
Right click on Command Prompt and Run As Admin.
Right click inside the Command Prompt widow and select Paste (or Edit then Paste). The copied line should appear.
A new Search & Indexing window should appear. Hit Next
Check all but the last box (My problem isn't listed.) Hit Next
If you get a screen that asks you to describe your problem just hit Next.
Does it claim it fixed anything?
If it says it can't fix it then see:
Scroll down to where it says:
Manually Reset Windows Search and Rebuild the Index
and follow the instructions.