It is possible that the updates are not uninstalling but proctecting. There are different viruses that can be allocated in the SearchHost.Exe. First I would recommend to run a Full Scan on your computer using Microsoft Defender, and check the Quarantine section to see if perhaps the executable has been put there.
On the other hand, you may want to check that the service is configured as "Automatic" using the next command from command prompt:
REG UPDATE HKLM\SYSTEM\CurrentControlSet\Services\WSearch\Start=1
Then restart Windows Search with:
net.exe stop "Windows Search"
net.exe start "Windows Search"
--If the reply is helpful, please Upvote and Accept as answer--