Determinism isn't essential to achieve record/playback experiences. You could just record the transform of the player at some fixed interval and then replay it with interpolation. This is arguably more "deterministic" in a strategic sense of shipping a viable product.

The player is just one entity, you'd need to do the same to any other non-trivial entity. And you couldn't use fixed intervals and naive interpolation, otherwise you'd have entities clipping the ground when bouncing etc.