Any new shortcuts I add to the start menu fail to show up in the start menu search results. I've tried rebuilding the index to no avail.
[Credit to CraigsNotHere on reddit]
Turns out the issue was due to having UAC disabled. To re-enable, simply toggle
User Account Control: Run all administrators in admin approval mode in your Group Policy Editor (gpedit), otherwise if you're running Windows Home, open up regedit and enable (set to 1)