Delete search "cache" in Windows 10 (search finding non-existent / old programs)

I was able to resolve my issue by enabling "Let apps run in the background." If you don't see the option in the Windows UI, you can still enable it via the registry. To do so;

1. Press windows logo key + R to open the run dialog. Type "regedit" then press enter.
2. Navigate to the following key: HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\BackgroundAccessApplications
3. Right click on BackgroundAccessApplications, and select New -> DWORD (32-bit) Value. Name it GlobalUserDisabled and set its value to 0.
4. Restart.

An additional step I performed in between 3 and 4 were to navigate to the key: HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\BackgroundAccessApplications\Microsoft.Windows.Cortana_... and set both the "disabled" and "disabledByUser" values to 0. I'm not sure that made a difference, but I'm including that as well, in case steps 1-4 do not do it for you.