Rewriting the user's entire database on each delete sounds like it might become a problem. Especially as some users like to automatically delete old posts on a regular basis.
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.