I wonder whether abstract interpretation could recover the missing codepaths more accurately. It sounds like some games, like Metroid 2, are missing quite a few codepaths because of potential actions which are available in the context of the quote but not used in the replay. I imagine that we could bound such abstract interpretation based on a limited number of divergent frames from the original quote; the quote might include all actions achievable within a few seconds or a minute of taking the controls, but still not the entire game.
This is very similar to the “lekktor” approach taken to shrink the .kkrieger binary.
Both seem to be unsound, dynamic approaches to program slicing.