It just seems as if there is going to have to be a compromise in the utility. Otherwise the script is going to have to evaluate a lot of different cases in order to successfully run:
- Is it the first post?

- If yes, are there replies to this post?

- Is this post a reply to another post?

- If yes, are there replies past this post?

...and so on
It seems like it would get very messy and complex. Especially if follow-up posts contained text originating within the offending post.
I like, personally, having posts with text akin to "Post deleted by administration." It provides a sense that there is some governing body on the board that's actively attempting to make my user experience as good as possible.
As for the offending username, you have two options:
1) Change the username in the portion of the script doing the query. Apply a moderator's name or something where the offending user's name appears, or

2) Alter the HTML at that portion so you have one single row spanning the two columns, and your "Deleted by..." text. Basically what you have is just a place holder in the post tree....
---------
Shalazar
<a target="_blank" href=http://www.charisma-carpenter.com>www.charisma-carpenter.com</a>