A review of your relationship settings included with this ticket indicates that for most of your relationships, you have the “Destination Item Deleted Resolution” set to “Delete Source”.  This creates a situation where deleting an item on any folder will cause the item to delete on all folders.  This is not a recommended configuration, as you have no control over the preservation of items.  While in most cases, users are not deleting each other’s items, there could be other factors at work (Handhelds with no free memory, Corrupted Outlook profile, etc.) which may delete items without the user’s knowledge.  Should one user delete an item and cause the item to be removed from all other users, the only way to identify the offender would be to check each user’s deleted items folders or check the “Recover Deleted Items” option on the public folder.

Our recommendation for a protected configuration would be to set the “Destination Item Deleted Resolution” to “Recopy Source Item”.  This makes your relationship deletion proof, and allows deletions to occur only at the Source, not at the Destinations.