The answer for AfD:
Get rid of it. Allow anyone to delete articles. Anyone who tries to create an article or clicks on a link to a deleted article will get the notification that previously deleted entries exist (the message that admins get for deleted articles). Allow anyone to view and restore those edits.
That is, because deletion is now non-destructive (i.e., reversible), there's no need to restrict the power -- or the power to restore. The rules about edit wars and reversions apply as normal.
Only exception: copyright infringement/illegal content. Those go through the AfD process, are hard-deleted. That's it.