That being said, Staff members can see VMs which are deleted if they want to. Currently we're only allowed to soft-delete them, which takes them out of public view. (doesn't remove them permanently.
Let me just specify and state that even moderators can't hard-delete visitor messages from profiles (their own or anyone else's for that matter), so gaining the ability to heard-delete visitor messages (even if that's not something you're suggesting along with being able to undelete visitor messages) just is entirely unlikely to happen.
Allow all users to specifically undelete VMs. This would essentially prevent anyone from posting something flaming in a VM then immediately deleting it afterward.
Though David already asked this, he has a good point. People say a lot of things that they don't necessarily mean in the heat of the moment. One minute, of course, when they're mad, they'll say something they later regret. For example to suite this suggestion, someone may flame you in a visitor message while you're offline and you log in to find that someone deleted a visitor message from your profile. Hypothetically speaking, you want to see what they said, so you undelete the message and read it. Growing enraged at what they're saying, you take it upon yourself to continue the argument or feed the flame that's already been put out for whatever reason.
Sure, you realize someone deleted that out of most likely feeling guilty, but after reading what they said about you in your public profile, you certainly want to take it upon yourself to confront them about what they had to say and only cause more problems that would have been caused if you just left it be.
I don't think members should be allowed to undelete messages previously deleted on their profile just because someone may have flamed you in a VM and you want to view but can't because they most likely regretted saying whatever it is they said in the first place. Sounds like the little drama queen in you is interested in causing something, if you ask me, which I know it most likely isn't, but still.
Sure, the message may be on your profile and may be directed at you, but it isn't yours to delete unless you feel insulted or something by it; in which case, you should delete the message, then contact a staff member for something to happen (most likely due to disrespect or something along those lines). With that said, I don't think members should even be able to delete visitor messages in the first place, but I really don't care either way because its nice to be able to remove something from your profile that you may not want there without relying on someone else to do it for you because that can make you feel tedious and bothersome.