I know of two ways: reinstalling the programs (even though they're still on the computer), and the hard way
The listings on the All Programs menu are really shortcuts. When you click them, they in effect click their target, which can be anywhere on your computer. For example, the Microsoft Word listing in my All Programs targets C:\Program Files\Microsoft Office\OFFICE11\WINWORD.EXE on my computer
Look in C:\Program Files for a folder named after either the program or its company. Inside it there's an application (ending .exe) with an icon that looks a lot like your missing program. (It's easier to find if you Arrange Icons By Type.) Right click it, select Create Shortcut, then drag the shortcut to the Start menu and into All Programs
The files may be hidden, so go to the Control Panel, then Folder Options, View tab, and choose Show Hidden Files and Folders
I'd try the reinstall first. :-