Actually for the longest time if you simply toggled:
Settings -> Background Apps -> "Let apps run in the background"
It would disable search even though nothing related to search was in the apps list (along with other presumably hidden items). The workaround was to leave background apps globally enabled and manually disable every app that showed in the list (including any that got added over time). I think this was finally fixed in 1809.
Presumably they - or some script they didn't really understand - turned off the "Let Windows track app launches to improve Start and search results" setting.