Games that use deterministic lockstep typically have more latency than other types of games.
I have written myself some pretty nice tools for debugging determinism issues, but it still took me several weeks to comb through the whole Cosmoteer codebase and convert everything to be deterministic. And non-determinism bugs can be very tricky to track down.
The gameplay really does have to be 100% deterministic.