Vista - "Recently Opened Programs" list and "Search for program" fail

I upgraded from Windows XP Tablet PC Edition to Windows Vista Business.
In Start Menu Properties under Privacy, I selected the (default) option
"Store and display a list of recently opened programs". After having opened a
program through "All programs", it is added to the list, but it seems to be
impossible to start programs from this list. Using right click + Open does
not help either. Pinning the program to the start menu does not change this.
If I search for an installed program other than Windows ingredients like
Calculator, e.g. Excel or Adobe Acrobat, it does find the program, but again,
starting it from the list is impossible. Searching for documents works fine,
and opening a document from the list happens quickly and without any problems.
The Event Viewer does not seem to list any errors related to this.
Any suggestions will be appreciated very much.