When I reboot the phone, often, some of the apps a get generic icon and won't load anymore.
A reinstall solves the problem but I'd rather not have to do that.
Device is an Acer Liquid Metal with Froyo.
I finally found out why! :D
When the phone boots - at least if I use go launcher - if the sd card is not completely mounted apps "get lost". I've completely solved the problem activating my phone card pin code. I turn on the phone, wait on the pin code screen without entering it for a minute and then I enter the pin: everything is perfect. I think the problem can be also solved killing and restarting the launcher but I didn't test.
Have you moved them to or from the SD card? My app icons disappear from my home screen when they are moved.
I sometimes have this problem with my LG Optimus V. I used to re-install the app(s), now I just reboot the phone again--works 9 times out of 10 (and with those odds, the a second reboot handles that 10th time).
Finally I found it
Settings > apps > apps settings > disable all apps > apps settings > enable all apps