I've encountered the same experience on some programs I installed in my ipaq1940. What I did was the same as suggested above but more specifically I searched for the link and delete it. For example you have a non-working link "deletedprogram.exe", open file explorer and search for "*.lnk" and probably you will find the "deletedprogram.lnk". Delete that and you'll never see the program's shortcut.