Applications Not Found

I've reinstalled windows several times since I've purchased Start8 and within weeks (sometimes days) it starts to not list applications I have installed when searched for, for example:

I click on the start menu and see the game "GalCiv2".

However, if I hit the windows key and type "GalCiv2" nothing it displayed.

This happens with numerous but seemingly random programs, even including the calculator once. I tried uninstalling/reinstalling and removing all registry entries in between and the problem persists. 

Let me know what you need to narrow down the issue. Considering you're working on Start10 (which I personally find hilarious) I'd definitely like to resolve this issue.

Note: this does not happen with the default start screen or other alternatives on Windows 8.1 64-bit.