Yes, the problem is that some applications install to the SD card without your knowing it or you've moved it there yourself. When the SD card is unmounted for some reason (I'm surprised it does it to you when you simply power off the phone) such as connecting to a PC or when you explicitly unmount it, those icons, which are shortcuts, lose the "connection" to what they are shortcuts to and, when you turn on the phone or remount the SD card, the OS apparently does not "remember" to point back to the application.
Since these phones are a "flavor" of Unix of some sort, this should work since it does so in HP-UX, AIX, IRIX, Linux, etc. Why it should fail is unknown to me.
The solution is to go to the applications manager (Settings, Applications) and select the On SD card tab. That will show you what apps are on the SD card. Moving them back to the phone (there should be more than enough room for all your apps and no need to put any on the SD card) will solve this unless an update moves the app back to the SD card (I've seen this many times.)
I hope this helps.