First Off Great Comment! Pretty much a full post in response to my post which is awesome. I can clearly see that you have put some serious thought into Private Messages. You have some great points here, I'll try to get to all of them, thanks for opening up the discussion. I was planning on going into more discussion and theory on this post but ended up just focusing on design.

I think there should be three different categories of PMs

This is a solid idea, I think by having these 3 types are a simple dropdown to tab based system would work well. This way, like you do with most spam and junk , be able to switch users between the categories easily. Notifications as you put it would work fine, and user settings n the client side would do the trick. For mobile this would extend to push notifications and alerts.

Do you consider the mute functionality described in your post the same as the existing mute function?

I was considering this mute button to be separate from the one on the block chain , which would be for you to see and not anyone else to know you have blocked that user. I do think that this may be something more on the lines of Public Messages like that of comments but on the blockchain for everyone to see... though this is a different discussion ;) A distinguishable mute for each would be appropriate I think.

Regarding indentation of your messages

Thanks for the suggestions, I actually looked at all sorts of Social Media to gain inspiration on this but ended up with the simple design you see above. I ended with this because I wasn't feeling any of the Normal type designs in regards to steemits design. Now that you point it out a single color difference between the messages maybe all we need. I just wanted to illustrate that we don't need over design here.

In regards to true deletion of messages its a toss up. We want everything to be on the blockchain but like you said messages would eventually be decrypted and you have all great points in that 3rd and closing paragraph. The false sense of security I am also very much against and this really opens up the conversation on if PMs could really be pulled off correctly.