- Delete the page table entry immediately (making the page and its
revisions invisible), and schedule moving/rev_deleting the revisions in the job queue. This will severely reduce the load of a delete request, but will delay the old revisions showing up in the undelete pool (the "undelete N deleted revisions?" link), making it hard/impossible to undelete a page shortly after deleting it. A solution could be to move/rev_delete the first revision immediately (i.e. right after deleting the page table entry) as well, so at least the most recent revision can be undeleted.
If you were really clever you could find the revisions in the job queue and then undelete them by just removing them from the queue - cancelling the deletion rather than undeleting it, in effect.