Looking at this, it occurred to me maybe we could maintain a count of deleted items in the cursor, which might address Alex's point by covering more obscure delete patterns, and we'd only need to check if the page should be pushed out when we switch pages?

This branch has been very lightly tested, it's mostly to show you what I mean.

I wasn't part of your and Alex's discussions on this one, so I may simply not understand the issues – if this is just wrong-headed, feel free to delete this branch without further discussion.