more specifically, the bug is due to a buffer overflow during paused chat, and presumably deviant undefined behavior between the original execution and the replayed execution.

and most importantly, it has nothing to do with the non-deterministic nature of the game -- non-determinism is trivial to account for, because PCRNGs are not actually non-deterministic; they're (pseudo)random, and deterministically so. They're just random enough to be equivalent to non-deterministic to the user.

As long as seeds are synced, it's trivially managed. But this kind of cause-for-desync is the reason deterministic engines are such a PITA to actually write. Any source of actual non-determinism wrecks everything, and there's always some miserably rare cases.

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.