Oh man. On Army of Two we were running a fully deterministic simulation and we had to patch many part of PhysX to maintain determinism. In the end, we had to get a waiver from Sony to ship a binary-patched version PhysX libraries. Good times.
Sounds like a potential GDC or Gamasutra writeup.
Otherwise you run into situation where large deltaV, or very small deltaV completely break the physics calculations. The next is that rounding issue and precision with double still creep in and having a physicist engine that is deterministic for a given hz and float/double speeds up development time.
When you replay a series of inputs, you want the accompanying physics to come out the same. Solvers that use randomness in your engine will either need to have their RNG seeded with the same value or have the rng removed.
Another thing causing problems might be how your engine handles time or when it iterates over objects in a specific order relative to how they were added (might not have preserved that order in your snapshot).
There's many things that can go wrong.
Knowing only how much Army of Two stressed its cooperative network play nature (including in its title), that's my best lay guess of the strong reason the game wanted deterministic simulations.
The impression I got from dev team discussions/features on The Halo Channel/Master Chief Collection was that Halo was built that way: its network engine wanted rock solid deterministic physics, so all the replay/recap features added to later games were a "free" bonus they were able to build on top from that earlier netcode requirement.
That also has the advantage of being able to "fake" events with effects until the server can resolve them meaning a latent connection can 'feel' faster.
Kudos to you for shipping a lockstep solution, we could never flush out the determinism bugs on our titles so we always just used dead-reckoning unless it was some dumb turn based game.
Another thing to consider about a replay system is that you don't have to be perfect. What you as a player see isn't what the server(if you have one) sees, and it's not what the other player sees. Your view is only a best guess at that, and for most replay systems in games, they will also be best guesses.
In terms of this game in particular, it's a multiplayer coop action shooter so you want everything the behave the same way on both players machines. The player models should be in consistent places in the world, bullets should fly in the same direction on both, grenades and other physics objects should bounce the same way.
If these things do not happen then you will have diverging realities on each of the machines.