If both sender and recipient of a PM deletes it, then it's deleted from the database completely and I can't access it except through the daily database backups. (This is a massive pain, so don't expect me to do it for you...)

Deleted/edited posts are always saved forever.