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.
If law enforcement requested it, how far back could you access? (Or how often do archives get purged?)