When searching in the Start menu of Windows 10, the results usually include items from the System Settings app. On a fresh install of Windows 10 Enterprise, either 1607 or 1511, this works as expected for the first user to logon.
After going through Windows update and creating a second local user (or, if joined to a domain, using a domain user to logon), Search doesn't work for this user. Results will not include any items from System settings.
This question already proposes a lot of troubleshooting of which I already tried everything. Maybe the most interesting thing is that the folder %LOCALAPPDATA%\Packages\windows.immersivecontrolpanel_cw5n1h2txyewy\LocalState
stays empty, while the same folder is populated with files in the first user's profile. Copying those files over makes search work, however, this is more of a workaround than an actual solution.
This might be related to a recent update, because both 1511 and 1607 without any updates installed are behaving correctly. I'm also using the German version of Windows, however, changing Language packs did not change search behaviour.