Windows search is integrated through the Start Menu, so when you see files that are the executable, that means that Windows search isn't showing you the start menu entry but the actual file.
Typically, a start menu link to an executable supersedes the executable name, so start menu search will only show one and not both. Once the start menu entry is missing, it will start showing you the .exe name and not the start menu link name.
So the problem remains that items are missing from your start menu. Did you make any changes to the computer recently? Otherwise this sort of behavior screams "virus," "torrented software," or "somebody else is messing with my computer." Do you use a password on the machine so kids/wife/friends/coworkers can't cause problems? Is the software authentic so automatic updates don't cause problems?
Are the links hidden or marked as system in C:\ProgramData\Microsoft\Windows\Start Menu\Programs\?
Sorry for the questions, I'll edit them out if you edit your question to include this information and I'll try to drop any better answer I can here.
1
Similar questions are here http://superuser.com/questions/21519/all-start-menu-items-have-disappeared and http://superuser.com/questions/131468/windows-7-start-menu-items-missing
– Dave – 2012-09-12T14:41:28.643Thanks, but unfortunately none of those applies. Folders are also missing in the folders noted in these threads. – stefan.at.wpf – 2012-09-12T14:48:32.250
Have you done a disk/file system check yet? – Ƭᴇcʜιᴇ007 – 2012-09-12T15:07:06.467