Unless, of course, you already need determinism for multi-player to work. Real time strategy games, first person shooters with complex AI, and other games that are networked in lock-step are
already completely deterministic and have to be for it to work at all. You basically get replays for free that way, but it has to be a conscious effort of the entire team to maintain determinism.
Luckily, determinism is something that you can verify with an automated process. After each checkin, run some automated tests on a server farm. Run them twice. During the first run, take a full game world state snapshot periodically. During the second run, verify that the world state is identical since the first run. If it isn't, re-run the test twice. Take snapshots more frequently during the interval where determinism broke. Recurse like a binary search. You can automatically pin-point the exact frame where the simulations diverge.
One you have a replay file and the exact frame, you have the best bug report on the planet. "This replay is build 12345 and crashes on frame 54321". Fire it up in the debugger, run a system command "fast forward to frame 54321" and then just start stepping. Oh, it crashes on that line? Let's drill into that: restart replay, set breakpoint, run to frame 54321, step-in. Freaking beautiful.