Looks like this KB is breaking search on some Windows 10 machines:
One fix is to roll back the patch:
https://social.technet.microsoft.com/Forums/en-US/c60d0c27-b294-4c55-ac4f-03c4f14bd89c/kb4512941-breaks-start-menu-searching?forum=win10itprogeneral
Or you can add these registry keys and restart the searchui process:
reg add HKCU\Software\Microsoft\Windows\CurrentVersion\Search /v BingSearchEnabled /t REG_DWORD /d 0 /f
reg add HKCU\Software\Microsoft\Windows\CurrentVersion\Search /v CortanaConsent /t REG_DWORD /d 0 /f
tskill searchui
Note: the above has to be run as the currently logged in user
I’m creating a worklet to automate the above, but it requires that the registry key be changed for each users which makes the code a bit more complex (example from PDQ here). In the meantime I wanted to help spread the word in case you’re getting tickets from your users about their search not working. You can at least remote into their machine and run the registry commands logged in as them (don’t run as administrator).