StarCraft Brood War replays would desync due to version issues, too. Any gameplay adjustments in a patch would affect the replay, often in subtle ways that would sometimes result in a valid and interesting game, just different outcome.