Never happens -- I install and uninstall crud all the time; no problem with uninstallers crashing if their icon isn't found. The only downside is if you move the icon the uninstaller won't find it.

I put all my Start Menu items in the same folder that contains the Programs folder. My programs folder then just contains the crud I haven't decided to keep yet or haven't otherwise organized.

I have ClassicShell configured so the class start menu appears if I click but the Win 7 start menu comes up if I use the keyboard (for searching).