Retrieving old/deleted messages
Not in any simple, user friendly way.

You're really wandering into the realm of digital forensics here, unless you can convince your carrier that it's worth their while to salvage something from their logs.

Or, y'know, ask your friendly NSA contacts ;p