I had the same problem, and yip it's so frustrating huh?!
It's caused by the program used to launch apps at power up. Apparently on a lot of android devices, apps moved to SD do not get loaded (or get partially loaded).
First I tried moving the apps back from SD card to phone. It did fix the issue...but because I kept running out of space on my phone, I had to move them back to SD and find another solution.
I found out (by digging around on my phone and a bit of luck) that when my shortcuts disappear all I have to do is clear the RAM memory. This closes the active apps and then reloads everything, including the apps on the SD card.
To get to RAM Manager on my Samsung Galaxy - I just long press on the Home Key which brings up Task Manager. Then I tap the Ram tab. In mine I have 2 levels, so I tap "level 2" and then "Clear Memory". In a few secs "Voila" shortcuts are back! Those with other devices, just find out how to access Task Manager or RAM and you'll be set.
I know this can be a wee bit annoying, having to do this whenever you power up. But it does mean I can store as many apps as possible to SD and access my apps with little fuss.
Hope this helps you
Oh but if anyone finds an even better way, please share.