I am having a similar problem today after attempting to copy some photos yesterday to my computer. My phone froze during the process and I ultimately had to take the battery out to reboot. After that, my start page was actually completely missing, but eventually got it back with a bunch of apps missing. Couldn't find them in the apps list display, but like you said the store said they were installed and could be opened from that point.
Turns out the buggered apps are on the SD card, trying to move a few to the phone and then back to the card didn't fix it. A subsequent restart of the phone now says the SD card has problems and should be scanned, but it doesn't do the scan. Botomline- I guess my SD card was glitched.
Any way to start the scan/repair of the card manually?