This sounds like exactly the situation where you would want to use a persistent tree. For a log(n) overhead, you can keep the ordering of all the messages in your mailbox at any given point in time. Then you don't need to inform clients unless a new message is added that they might want to reference. Otherwise you just keep track of the state that client is operating on and use the old state to let you apply their actions to the new state.