What I have seen is the uninstall can only (automatically) remove files that were physically part of the install. Any files that get created during run-time or copied in manually will be left behind. Are the desktop icons part of the install? Or are they generated by a script that executes during the install? If it's the latter, based on the above statement, I could see why they wouldn't be removed. You can always write Custom Actions to do the necessary cleanup on uninstall. Hope this helps.
... View more