Another option #12
Description
Your mileage may vary, but I encountered the issue with icons not appearing in search and after reading the README in this repo, the faster solution for me was to actually just delete the entire %localappdata%\Packages\Microsoft.Windows.Search_cw5n1h2txyewy\LocalState folder, and then reboot twice. After the first reboot, search did not work at all (wouldn't respond to typing in the start menu and I could not put focus into the search box on the taskbar. After the second reboot, search was back and working correctly (a little slow, though... since I suspect it's rebuilding its index).
As an aside: I had also tried the Search troubleshooter built into Windows 10 and it didn't help at all. In fact, I ran it for the icons issue and then after it was done, search didn't work at all until my next reboot. Then... the icons issue came back. So, I was only able to fix by dropping the local state for search.
I do not see a problem with clearing local state for the app. Think about it -- when you install an app fresh (e.g., UWP, Android, iOS, etc.), they start with no local state.