My Story so far:
There are three problems to deal with. The first is what was causing all these documents to dissappear. The second is trying to recover the lost documents. The third is maintaining a backup so if this happens again, recovery is possible and easy.
I spent many hours on the phone with apple reps to try and determine what the cause of the problem is. We were able to reproduce the problem by simply turning off my new iPhone 4S and turning it back on. This would cause a sync that removed all documents from iCloud. Essentially anytime I restarted my 4S it would delete all that data.
This seems to be related to all the activation problems. Those of us that had these activation problems may have also triggerred iCloud to be setup incorrectly on our device. This is just a guess. It was not happening on my iPhone 4.
To fix this we simply had to sign out of iCloud in the iCloud settings page and sign back in. It asks you about removing the data from the device or not (it's up to you, iCloud was keeping everything else safe for me and I had Time machine backups of address book and calendar data on my mac). We then went to all my other iCloud enabled devices and restarted them one at a time to make sure they weren't suffering from the same bug. If documents dissappeared that device would need to be signed out of iCloud and signed back in.
For now, my documents have been "stable" since doing this (at least a week). Now onto issue 2 recovering the lost documents.
The "deletedAt" folder. I have personally not seen this. For those of you with an hourly backup and constantly connected time machine backup with documents enabled on icloud on your mac, you have the possibility of recovering your documents from some point in time. I was lucky to have a time machine backup of a version of all the most important files in the Library/Mobile Documents folder from the day before the loss. I just happened to plugin my time machine backup and do a backup the day before. I recovered everything "important".
Apple has officially told me that since the documents were not lost due to a server side bug, they can't get any backups. Essentially the iPhone 4S told iCloud to remove all these documents and iCould did exactly what it was told to do. The bug is in the software for iOS. Again, probably due to activation problems for us early adoptors.
Issue 3 Preventing future issues. Documents and Data are now being synced properly and instantly between all my devices. I moved my Time Machine backup to be network based so it is connected all the time (attached to my airporte extreme). I will now have backups of the Mobile Documents folder. Assuming that conitunes to work correctly, I can always restore recent documents back to iCloud directly from my mac. Apple, however, is not giving any assurances that data will sync to my Mac all the time. It took several days for the sync to happen after it was enabled. This may not be entirely stable.
Unfortunately there is no way I know of to move back to MobileMe. I am exploring that issue with Apple reps as I am not entirely comfortable with the above solutions.
That's my full report. I returned my iPhone 4S as apple was unwilling to provide any reasonable compensation for data loss. I encourage others experiencing this problem to do the same.
Message was edited by: dleute