This seems to be a common problem, but I have been so far unable to find a solution. The only thing that seems to be confirmed is that only the apps that are installed on an SD card disappear, while the ones installed on the internal memory don’t have this problem. Is this the same for you too? Are you using any desktop replacement app?
I'm not using a desktop replacement, but I
have shoved a big-ass micro-SDHC card in and told Android to use it as the default for storage. Sigh. Now going through my app settings to move the disappearing ones to internal storage ...
Edit: And yes, moving those apps explicitly to internal storage seems to have fixed the disappearing-on-reboot problem.