Ever since my laptop was updated from Windows 8.1 to Windows 10 through Windows Update, the search feature has been behaving very poorly due to some past damage buried deep in Windows, its registry or somewhere within/around the Indexing service. This post is not about discussing what might be causing all these issues, but to provide a workaround which might work for some instances of two specific symptoms: missing searched items in the start menu, including items from the Control Panel, and a constant warning claiming that "These results may be incomplete..." as can be seen in the partial screenshot below.
At the end of the post I provide links to discussions and suggestions I found about the same symptoms, although none of them provided this new solution which, so far, is the single one that worked in my setup. Be sure to check them first.
This workaround was applied to the latest Windows update to version 1511 (build 10586), as the update itself did not fix anything in my setup.
The workaround is simple, just fire up the Indexing options and add the following directory to the indexed locations: C:\Users\YOUR_USER\AppData\Local\Packages\windows.immersivecontrolpanel_cw5n1h2txyewy\LocalState.
If your issue is somehow caused by the immersive control panel (also why control panel items might be missing from search), then hopefully this will work. Meanwhile, you might have difficulty finding the Indexing options because of this exact problem, so you can just call it directly by inserting rundll32.exe shell32.dll,Control_RunDLL srchadmin.dll on the Run dialog (WINKEY+R).
-  Can't find Start Menu items via search anymore, any way I can get them back?
-  No settings or control panel items in search
-  How To Fix Windows 10 Search Issues By Rebuilding Index
-  Windows 10 Search Function Issue- "These results may be incomplete...". Any idea how to fix this?
-  [Fix] We’re Getting Search Ready Problem in Windows 10
-  Why is my start menu not working in the Windows 10 upgrade?