We've come across a scenario in production (noticed on Cassandra 2.2.14) where data that is deleted from Cassandra at consistency ALL can be resurrected. I've added a reproduction in a comment.
If a delete is issued during a range movement (i.e. bootstrap, decommission, move), and gc_grace_seconds is surpassed before the stream is finished, then the tombstones from the delete can be purged from the recipient node before the data is streamed. Once the move is complete, the data now exists on the recipient node without a tombstone.
We noticed this because our bootstrapping time occasionally exceeds our configured gc_grace_seconds, so we lose the consistency guarantee. As an operator, it would be great to not have to worry about this edge case.
I've attached a patch that we have tested and successfully used in production, and haven't noticed any ill effects. Happy to submit patches for more recent versions, I'm not sure how cleanly this will actually merge since there was some refactoring to this logic in 3.x.