We have also experienced something like this. Sometimes content just dissapeared, but this had to do with the caching-system in eZ publish. If we ran clearcache.sh a couple of times, then the content was available again.
Frustrating, but it seems stable now(..a couple of bugs which are fixed).
I guess this is a little bit different from your case, but have you done a -grep in the ez-admin-access.log to see if these objects are edited and deleted by editors and not by the workflow? Maybe you should add some logging in the workflow, so you can see which objects are beeing removed..
Btw. you write: "I have also seen occurrences of users drafts containing draft versions of deleted (non existent) objects."
If this is the case then the eZ Crew must change some code here. When an object is deleted, the version-history also have to be updated..maybe some caching-problems??
In my case, this was caused by not having transaction support enabled i combination with php timeout. During a simple save of node containing many subnodes, all the content under the node was lost. To be more accurate, objects are still there, but there is no connection to corresponding nodes.
Since that incident, I never intend to use non-transactional setting.
