Ideal replay systems don't depend on the exactness of floating point numbers.
All of the actual logic and events can be recorded. That is, you don't just record "fired bullet at pos 3.4,5.2 at vel 1.2,-0.8" and then expect the client to re-execute the bullet collision logic. You record both that the bullet was fired and that the bullet collided with something (and where) and what the results of that collision where. At appropriate time points, the replay data will "correct" any values (that is, after an object bounces, the replay records the new position and velocity, rather than expecting the client to recalculate those).
This is the exact same as network synchronization. A lot of games with replay systems in fact reuse their network infrastructure, since replay data can be the exact same as the data sent to spectator clients.
Thus your replays might at worst have some very slight discrepancies visually (highly unlikely to be noticeable), but the replay will still play out mechanically the exact same. Those discrepancies will not be vital to the game itself, and hence you can completely ignore the potential inaccuracies of floating point numbers.
Also keep in mind that those discrepancies will never really happen on most real hardware, because a replay of SC2 is always played back on the same CPU architecture. That is, you aren't going to be recording a session on an x86 CPU and then playing it back on an ARM CPU, because there is only an x86 SC2 client. Same goes for most other games.
The only "hard" part is going to be synchronizing time steps so that events are firing in the proper sequence and at the proper speed, but that's mostly solved by just using fixed time steps.