The way I remember it was that replay playback would only break if you played a replay with a different game version than it was recorded with.
or, if you are replaying a single-player game that you saved+loaded (i.e. the replay only worked if the full game happened in one go without any loads).
There was definitely sync bugs with replays at various points.
There was even desync bugs even in live multiplayer games; there was detection that it desynced which would end the game, which in turn meant exploits that would intentionally cause a desync (which would typically involve cancelled zerg buildings for some reason).