The root gets updated with each update, and the diff gets exchanged as part of the sync protocol. Deleting and purging is no different than other federated protocols in that regard.
Why use a merkle tree if you need to give users the ability to remove stuff?
Just store it in some other struct and have each message signed by the user. Let them add and remove messages at will.