That one is the relatively easy bit to solve - you don't ever delete a post, you just delete the content, and make it a null, invisible node - so that all the succeeding nodes can be linked to it. But then you have the problem of quotes in succeeding posts, what if they contained the text that caused the post to be deleted? So now all succeeding posts need to be searched and any quotes within purged. If you'd thought of this before you started, you'd make quotes references to the original post rather than copying the context across - that's a better solution, but it fundamentally changes the underlying structures. So, you go back to post purging, which is problematic in its own way. Moderation facilities make these features much more difficult. It's helped here by the fact that we hardly ever delete posts, rather we move them to the Dumpster. That will be easier with an embedded threaded structure, because whole subthread can be moved in one go. But it leaves the problem that posts which contribute positively to the original thread end up in the Dumpster. The model of threading that I'm using, which is based on post order rather than linked lists helps that, in that relative ordering can be retained even if a few posts are removed.
The efficiency problem can be fixed if the whole site is based on a suitable structure, called a B-tree. It isn't here or on DPReview, and it's a pretty fundamental change. The underlying Django and Postgres systems on which these forums are based allow B-tree searching, but because they aren't the underlying structure they are implemented using separate data indexes which can become very large indeed. I'm addressing this problem by only implementing threaded order within a thread, which slightly complicates the reordering problem above and depends on facilitators doing the job properly when they move a sub-thread. So, they can prune a branch, but decide to leave some posts unpruned, and those posts go at the right place in the original thread. Once they've been put in another thread, putting them back in the right place becomes more difficult.
This might be a bit technical for some, but it's just to show that it is being done and that it isn't simple.