Android devices can mount loopback file systems, overcoming FAT's lack of unix permissions. They did it to install Debian on the G1's SD card.
Yes, and as I said, this is exactly what I keep hearing about as the long-term plan. The problem as I understand it is that it will require significant developer time to write an implementation. The easy part is automatically generating, mounting, and unmounting the encrypted loopbacks as needed. The hard part is changing Dalvik, the GUI, etc. so that they all do something sensible when the SD card is yanked out.
(The naïve solution of "SIGSTOP the missing apps until the SD card is reinserted" could well leave the phone effectively hosed if the app was running in the foreground. There are plenty of full-screen apps that hide the notification panel, and apps can capture a surprisingly large set of keypresses — and games, the most likely candidates for installing to an SD card, are also the most likely candidates for capturing keystrokes and going full-screen. Most users won't care that adb shell still works fine.)
Disclaimer: I work at Google, but not on Android and definitely not as a spokesman for Android, and I would be quite shocked if any of this were news outside the company. I'm fairly sure the bulk of this discussion exists in the public Android bug tracking system, as I remember being pointed there when we all got our shiny ADP1s a year ago and the same question came up. At any rate, the problem space is well known since it afflicts non-Android Linux (esp. Knoppix and other removable-media distros, which solve the problem by copying the entire system image to a RAMdisk).