I think we may be defining this term differently, and that's leading to many/most of your concerns.

I'm using 'unshallow' in the same sense that the git pack protocol does--a commit which the client DOES have, but which it used to have marked as shallow (which means 'this commit claims to have parents, but pretend that it doesn't because we didn't download them'.)  If we're deepening the tree, the client needs to remove the marking on these commits, since afterward it will have their parents just like any other commit.

Thus, these commits represent the last commit in the chain that the client has.  Anything beyond this which still passes the depth test is a new commit which must be sent to the client.  Since the client has all UNSHALLOW commits, they should be marked as UNINTERESTING as well, which is normally carried to all ancestors.  This is based on the assumption that if we have a commit, we always have its parents.  But in this case, that is not true, so we need to get rid of the UNINTERESTING flag on these ancestor commits, to tell the rest of the machinery that they need to be sent across.  To accomplish that, I carry the REINTERESTING flag to every commit below an UNSHALLOW commit, to denote that even though it's marked as UNINTERESTING, it's really lying.

Does that clear anything up?  Or are there still corner cases in the algorithm if it's done this way?