Hi veren. From my observations, here is it how it worked.
In Windows XP/Vista,
1. A shortcut to the app has to be present in the Start Menu
2. The app can be started from other locations such as the Desktop or Run dialog. As long as its shortcut is in the menu, it will show up in the MFU list.
In Windows 7/8, MS changed it so:
1. A shortcut to the app has to be present in the Start Menu
2. The app has to be started at least once from the Start Menu. If it isn't launched from Start Menu, then it won't show up in the MFU list.
3. Thereafter the app can be started from other locations such as the Desktop to show up in the MFU list.
Also, app shortcuts pinned to the Taskbar never show up in the MFU list. That is certain.
I will check the MFU behavior for Desktop and other places again to be 100% sure but try starting it once from the Start Menu, and see if it starts showing up.

Edit: Yes that's how it works. Confirmed. The Windows 7 original menu behaves the same way for me.