Coupla different things:
1) With your Pocket PC synced up to your computer over Active Sync, browse the Pocket PC files on your desktop. I think if you look under "Start Menu" you should be able to find the shortcut and delete it manually. (I'm not sure of the exact path - I don't have my Pocket PC synced up. If you can't find the Start Menu/shortcuts, check under Tools, Folder Options to make sure you can view hidden files.
Or you could
2) Install
Remover. This program will automatically delete invalid shortcuts, as well as cleaning up any "leftovers" that may remain from old "uninstalled" programs. I highly recommend this program. It's simple and easy to use, and it's free.