Brion-
To make it actually possible for human beings to get into the undeletion system?
Many months ago I made myself a little custom keyword for undeleting pages: http://www.mozilla.org/docs/end-user/keywords.html When I want to do so, I just type "und page_name". While this is a hack and you are correct that a proper action log table and a redesigned undeletion interface would be preferable, I do not see the information that deleted revisions exist as so useful as to have it on all pages, primarily because there's simply a fairly large number of pages which have been experimentally created at one point, deleted, and recreated.
How about displaying it in the top bar only for non-existing pages, and otherwise displaying it only on "Page history"? This should also reduce the number of checks in the ARCHIVE table needed.
Regards,
Erik