It sounds like it must be a case of not looking in the right place then.
Could you find the shortcut to CCleaner in all programs and right click it, pick properties and see where the shortcut itself (not the app) is stored. This should be on the general page I think.
That was a good idea. I see a clear pattern below:
SEARCH DOES NOT WORK:
Internet Explorer.lnk - C:\Users\<User Name>\AppData\Roaming\Microsoft\Windows\Start Menu\Programs
CCleaner.lnk - C:\Users\<User Name>\AppData\Roaming\Microsoft\Windows\Start Menu\Programs
Notepad.lnk - C:\Users\<User Name>\AppData\Roaming\Microsoft\Windows\Start Menu\Programs\Accessories
Skydrive.lnk - C:\Users\Default\AppData\Roaming\Microsoft\Windows\Start Menu\Programs
SEARCH DOES WORK (But the search results often include extra links under the "Programs" heading - links to the program EXE, INI, Help File, pretty much anything with the same name and in the target directory):
Outlook.lnk - C:\ProgramData\Microsoft\Windows\Start Menu\Programs\StartUp
Calculator.lnk - C:\ProgramData\Microsoft\Windows\Start Menu\Programs\Accessories
Chrome.lnk - C:\ProgramData\Microsoft\Windows\Start Menu\Programs\Google Chrome
MY INDEX SETTINGS:
Included Locations Excluded
Main (C:) ProgramData;CSC
Microsoft Office Outlook
Start Menu