Mercurial took an interesting approach here. It stores commits as diffs with occasional snapshots in between. This is similar to how video codecs store frames as deltas with occasional full 'keyframes' in between. This is the way Mercurial blunts the diff-replay problem you mentioned.

Git AFAIK, stores each file modification as full snapshot, until it is packed at some stage. Mercurial doesn't need this work around. Mercurial diffs are also format-neutral. It works fine with binary data.