There's a reason there were no complex-state MMOs at that time -- there simply wasn't the residential bandwidth to perform continual full state updates (latency aside).

E.g. grid & turn-based vs 3-D free-motion worlds

They say they specifically made the deterministic lockstep choice because it was the only option that (a) allowed the multiplayer gameplay they wanted and (b) fit within the computing and network resources of the time.