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.
