I've come across a revision in the 'revision' table that does not have a matching record in the 'page' table. It appears that this revision was created when renaming the page before it was deleted. It seems to me that this should be impossible within the constraints of MediaWiki's use of the database. If I'm right, this implies a bug.
See relevant queries here: http://quarry.wmflabs.org/query/3965