Here is my idea:
As The Cunctator noted, deletions are effectively irreversible, since there is no straightforward way for even a sysop to get at the deleted page, archived though it may be. We should change this.
I propose that any logged in user have the option to delete pages, just as they all have the option to move pages today. But this will not really delete the page from the database! The page is still there, and if you go to it, you can look at its history to see what it used to say. You can even revert it to undelete the page if you wish. The deletion will show up in [[Special:Recentchanges]] and [[Special:Watchlist]], where we will see that it has been deleted, with summary text similar to the text on [[Wikipedia:Deleted pages]] (which the deleter will have provided in a form just as sysops do today when they delete pages). These pages and article histories can have a "D" flag by the edit, similar to the "N" for new pages and the "M" for minor edits.
The deleted page shouldn't show up in [[Special:Allpages]]. A link to the deleted page should have a "?" (or red colour). You'll be allowed to move pages to these deleted pages (swapping histories since we want to preserve them). For all intents and purposes, the page appears to be gone, but when you go to it, you can find stuff in the history still. The database will know to treat the page in this fashion, because a new Boolean field will have a flag saying that it's been deleted.
To make this really work well, we should include one more thing: the ability to delete individual versions from a page's history. This would be used to remove copyright violations, and for no other reason. There are many copyright violations hidden in pages' histories now, and we are technically in violation of copyright for having them, however unobvious it may be for somebody to get to them. So we need to do this anyway, as has been suggested before. Only sysops would be able to do this, with a "del" link next to the "diff" and "cur" links in each page's history.
Benefits of my proposal: * Forces us to deal with copyright violations in histories. * Allows people to restore wrongly deleted pages easily. * Makes it much safer to delete useless stubs without hassle. * Lets people know if a page on their watchlist has been deleted. * Allows people to reverse redirects by moving pages without being a sysop. (You delete the target, then move the source to the target.)
It also obviates the need for [[Wikipedia:Deleted pages]], but this needs to be replaced with [[Special:Deletedhistories]] (to track deletions of copyright violations in histories), so that isn't really a benefit.
I believe that this proposal would be very helpful to all of us. The Cunctator will be able to rest easy knowing that no information has been lost when Andre deletes a page, and Andre will be able to delete truly useless pages without getting The Cunctator on his case about it. We'll still need a deletion policy to prevent edit wars (of a delete/revert variety), but it won't have to be as strict. Deletion will be just another edit, like the rest of Wikipedia (except for deletion of copyright violations, which we *should* be tough on).
-- Toby