You don't need to tun the whole game at a fixed framerate, only the physics. That's actually common practice.

The bigger problem is that floating point math isn't deterministic. So replays need to save key frames to avoid drift.

Quake used fixed point math.