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.

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).

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).