> ... or you accept that replays quickly become outdated

That's how Warcraft 3's fully deterministic save files would work. Old replay files would only work tied to one specific patch patch of the game.

But here's the thing: it's still a godsend while in development and it was still a godsend to players too. "Battlenet user spiritwolf beat me even though I had the upper hand, how did he do it? Let's check the replay immediately".

Also if you really think about it: if you plan for it from day one, there's not much preventing your game engine from having a pluggable system where you could have the various different patches of the game engine ship with every subsequent release of the game.

So when 1.03c is out but you want to play a replay meant for version 1.02b, the game automatically just use that version of the game engine.

The only case where this basically ain't working is if there's a patch for a security exploit: that'd probably need to be patched for good.

But for all other cases, backward compatibility for replay files / deterministic game engines is totally doable. It may not be how things are done, but it's totally doable.