This is the best suggestion i could think of short of making a view recent Private Messages feature that only the user could see.
My suggestion is to add an "Do archive" of private message button next to every Private Message and also make the output html by default. I don't think most users notice the archive messages link or even know what it does. This is just to make the archive feature more user friendly.
Here is an example of my site suggestion. I blacked out the subject of my private messages, who they were from, and my taskbar for privacy reasons.