I queried with HQ when I first had this, as whilst I accept someone may wish to delete their message, I think it is unacceptable that your message can be deleted. They said that was the procedure.
Also as someone has mentioned, often with pm’s you may give more personal info such as a private email address, I had expected that this was indeed private, but if someone can randomly delete ‘your’ message, then obviously access to these pm’s are not private at all. Watching this thread with interest!