Further to my earlier post about "All Pages, Including Deleted" broken, I have tested this on a new vanilla install untainted by any subsite pollution.
I belive this feature to be significantly broken mostly because get_including_deleted() uses a"latest_version" case in Versioned.php augmentSQL(). The observed behaviour mimics what the code should do.
Try this. Create a new page and then delete it. Do it as draft only or publish it then unpublish and delete draft. When you delete it you will see it appear as a marked deletion until you do a refresh and then it's gone. For good. Selecting the view "All Pages, Including Deleted" does not reveal the missing file because it's not in the SiteTree table. The function I believe is very broken.
If I am wrong or barking up the wrong tree please tell me and put me out of my misery or what the devil I have done wrong. I have spent nearly a week chasing my tail on this one and have posted several times about it.