If the applications have really been deleted, check via activesync add/remove programs, you can then navigate using either activesync and explore device or the filemanager on the device itself, to the \Windows\Start Menu directory on the device and delete the deleted items shortcuts.