Another idea: Why not see page deletion as and "end of life" marker in the page history? Let a page get a life cycle (create, change, delete).
That's what is currently in the document. It has the couple of obvious bad sides, like the fact what happens if someone recreates the page? Your versioning would not start from one, but 2389 ;-)
/Janne
