Really nice explanation! Wish I had known about this earlier 
I am currently in exactly that state where snapshots that are on my backup target server have already been pruned on my source machine. This would have saved me so much trouble.
Now I have to figure out how to re-transfer 2TiB of data - in the end probably physical transfer will be fastest with my upload speed.
Though I think there is a small mistake in your explanation.
From my understanding the bookmark does not work by the target sending back a list of data in the previous snapshot or something like that.
Actually that wouldn’t even be possible. You don’t need any bidirectional communication for a zfs send. You can even do `zfs send` on your source machine, write the output to a file, put it on an external drive, send it by mail (if your attachment limit is big enough or your dataset small enough xD), print it out or whatever. `zfs receive` simply consumes that datastream whenever you want it to.
Instead it seems to work with a generational counter (the TXG you mentioned). The source machine can just traverse it’s ZFS tree and check for each node “were you already there when the last snapshot was transferred?”, because they all store the TXG counter when they were created (that whole CoW concept of ZFS). If yes, skip (destination will already have it), if not, include in stream (was created since the last snapshot).