A game having random mechanisms has absolutely nothing to do with whether it's deterministic.
Slay the spire is 100% deterministic, gameplay-wise. All the online poker games too.
Here's an old forum post discussing it
https://tl.net/forum/brood-war/352588-my-replays-are-broken
Here's a hacky patch that also documents some of the possible issues
https://liquipedia.net/starcraft/Replay_Fix_for_1.16.1
It seems like the bug is related to pausing the game.
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.