How did you install the programs?
In linux, when you install something, the files usually goes into different directories. The main executive files(the so-called exe files in Windows) will normally go into directories like /usr/bin, /usr/sbin, etc. If you compile the applications from source, they will instead go into /usr/local/bin, /usr/local/sbin, etc. 3-rd party applications sometimes go into /opt/.
So, try to look for them in these folders.
I think most applications installed through the package management system in a modern distro should add a link in the menu. If the link doesn't show up, it usually means that the app is supposed to run in a console environment. Well, in your case, the yahoo messenger, should have a link in the menu, though. Just find it out and add it back.
Tips: No matter how you hate the console, it can be your best friend in solving problems, so don't be afraid of it. For example, when you try to look for an app, what you will do is to type:
Hope this helps.