If it's not somewhere in the Programs list then it wont show in the recently used programs (I'm assuming we're talking about Windows XP here). Navigate to c:\Program Files\Internet Explorer\ and ensure that you have the file IEXPLORE.EXE. Run it to confirm that it still works and you can re-create a shortcut in the Programs menu.