I have been having this problem on stock 5.68 for a long time now, and yes, it is always with apps that have been moved to the media area.
The weird thing is, I figured out that the apps aren't actually gone, it's more like the launcher or Android itself sort of 'forgets' that they are there. For example, and this is coming straight from my phone, say you've got Evernote installed and moved to the media area. Then, one day it doesn't show up in your launcher, and if you're using the separate Evernote Widget app (like I am), it displays a message like "You need the Evernote app to use this widget".
Now, if you go into Settings>Applications>Manage applications, and scroll through the list to about C, you will find an entry for the Evernote app called something like "com.evernote.(something)", and the system says it's sitting on the internal SD card or Media Area. In my experience, while it's gone, if I try to move it back to the phone, I get the error message "Sorry, this app does not exist" or something, and it fails. Sometimes if I reboot, and wait to unlock the lockscreen until the SD card notification goes away after booting, the missing app will reappear like nothing happened. Lots of times, though, I don't feel like rebooting or something and I just reinstall the app; that seems to both correct the problem of the app being installed/present AND remove the phantom "com.evernote.(whatever)" entry in Applications.
Sure would like it if this never happened again, though.
I don't seem to notice this issue nearly as often when I'm using a nonstandard launcher either, usually LauncherPro for me. Can anyone else confirm or notice if this is a stock launcher issue somehow, or deeper, something with the OS itself?
FWIW, I used to see this issue occasionally on my Atrix also, same circumstances, only apps moved to media area. I don't use an external SD card, so I've never experimented with that either, moving apps to a physical card instead.