Run cmd.exe as Administrator and execute the following command:
When your search doesn't work and Windows troubleshooting says the permissions are wrong, but cannot fix it, run the following command to fix the permissions and your search probably works, again (immediately).
takeown.exe /R /F C:\ProgramData\Microsoft\Search\
if it still doesn't work run
takeown.exe /R /F C:\ProgramData\Microsoft\
It thought, it works. But it only works for a short time, after which the permission issues are back, again.
Also didn't help: https://superuser.com/a/1353155