Administrators can use Special:DeletedContributions to search for user contributions that have been deleted before. However, most users gain many deleted contribs over time, maybe by patrolling new pages, or by doing simple mistakes. Reviewing these revisions would make many things easier, especially for newbies:

• After a sysop deleted your work, you can review what you did wrong to understand his concerns. You can still see a record of your work, it isn't gone.
• You can comprehend your own wiki-history even years later and do some statistics.
• Really problematic things are hidden by oversight anyway.

However, this also introduces some problems:

• You can just repost deleted content if you can read it.
• The associated copyright information is missing.
• Some content is deleted because of prrivacy issues or because they are offending. They shouldn't resurface.
• Deleted revisions shouldn't be a private information store for users.

That's why I propose introducing two new permissions: mydeletedhistory and mydeletedtext, analogous to the existing permissions, but just for own revisions. While I intend the latter for third-party wikis, I thing the first one can actually be useful on WMF-wikis as well, as it mitigates the problems mentioned before almost entirely while preserving major parts of the benefits.

In UI, I propose

• Showing the "Deleted contributions" links for users with mydeletedhistory on Special:Contributions/me
• Forwarding from "Special:DeletedContributions" to "Special:Contributions/me" if you have mydeletedhistory, but no deletedhistory
• Greying out "IP address or username:" field at the special page (containing the own user name). If the user would query the information about another user, he would get a permission error.

API changes might be required as well.