For deleted items, could you not store a memo of the object in addition to the user-local changes they did?
So if you undo a change to an object that was delete by a different user, you can restore that object first to the last known state, then apply the undo?
I'm not sure this makes sense for other cases besides object deletion.