Fast Boot option may be the culprit
I see folks here are deep into ext3/ext4 partitions and such (or at least you were a few months ago), and I hope it all works out great for you.
Just in case, here is a simple little fix that really helped me, without resorting to all the partitioning and reinstallation going on here.
Also, for what it's worth, I used ROM Manager Pro to auto-format the special "ext" partition on my sdcard when it was pristine, and since then have used Titanium Backup Pro to move apps to SD AFTER installing via Google Play Store or very occasionally side-installing .apk files.
CUT TO THE SOLUTION BELOW -- SEARCH FOR ////
Some (not all) of my apps moved to SD (all by Titanium Backup Pro) have begun to disappear and (sometimes) reappear without warning after I began to add and delete large Virtual Machines created in QEMU from my 16GB SanDisc class 10 microSD card on my HTC Droid Incredible running rooted stock Verizon Android Froyo 2.2.3. I know this thread is far from my phone's "home base", but from what I can tell this problem with disappearing apps located on an sdcard is NOT determined by hardware or even Android version.
I also happen to use LauncherPro by Federico Carnales instead of the built-in HTC Sense launcher. I noted elsewhere on XDA that a user had suggested that because at least some (maybe all) launchers start before the SD Card that this may be a problem, especially if changes are made to the sdcard that the launcher did not perform, or was not active during their performance by other apps such as Titanium Backup. That fits my situation, because I unmounted the SD, physically removed it to a PC, and added/deleted large VM files to save (lots) of time. No problems of this sort before I did this, so there must be some connection.
I noted that other users have tried reformatting SD, substituting different brands of SD, using newer/older SD etc. None of these reliably helped. So I skipped these options.
The (simple!) solution I tried that SEEMS to work (only time will tell!) is buried in the main Android Settings (accessed from the Menu button while in Home screen). Under "Applications" there is a setting "Fast Boot" that I checked long ago and forgot about (it seemed like a good thing to do at the time). The text warns "Turn off to use some Market apps" (that shows the age of my 2-yr old used phone and Android OS -- ohmygosh!-- because it refers to Market rather than Google Play Store!) Anyway, I unchecked the option and rebooted the phone.
Yes, it took a bit longer to boot (maybe a whole minute!), but after waiting about another minute ALL my home screen apps had normal icons and loaded properly. Titanium Backup Pro batch scenarios confirmed there were no apps in a forced uninstalled state (i.e. I had not done the deed, the system somehow had done it or at least rendered the apps "invisible" to Titanium, which decided they needed reinstallation).
The only odd behaviour was that auto brightness was turned off after I unchecked Fast Boot and rebooted. Going into Android Settings > Display and rechecking "auto brightness" took care of that. No other oddities or strange behaviours thus far (but it has only been about an hour).
I will report back here on this thread only (Samsung Fascinate > Fascinate Q&A > What just happend? apps on sdcard) if anything else requires reporting. Silence implies success!
(I am copying this post to other relevant threads, but will not post anything further elsewhere -- only there. This is a bit arbitrary (although this thread appears to be the most recent active one on this topic), but I hope this approach pleases the XDA sysops/admins)