I also think you need to apply some realism to combat...Other wise you get the scenarios like the ones people have described here. My favorite paradoxical scenario is, the baseball diamond with three characters and two monsters, one monster at 1st and 3rd and one character at 2nd, but two at home.
The round begins, one of the guys at home moves 30 feet, then charges 30 feet to the monster at 1st, swinging at them. The monster then moves toward the guy at 2nd, provoking an AoO, and charges...moving another 60 feet...this keeps going with the monster at 3rd charging the guy at home and the guy at home retreating to 1st.
So, in this scenario, you can seen that by viewing the attacks as passing a baton, you essentially had the baton travel, 60 to 1st, then 60 to and, then 3rd, and home, and finally to 1st...300 feet in 6 seconds. That is faster than an Olympic runner, and these guys are likely armored (no move penalty) with some other equipment.
I think the easiest way to handle this paradox, by injecting realism, by do a quick "go around" asking everyone in order of init what they are doing, followed by the game mechanics and actual movement and attacking.
In practice this results in creatures already dead having attacks wasted on them, because the guy that went right before them dropped them, attacks being wasted on creatures that fled the scene faster than the attack could get to them...but that's more realistic anyway. On top of this it adds more chaos into combat and allows creatures to do a little more with less, so fights can be easier in difficulty, because the added confusion and wasted actions to "be sure" essentially all happen simultaneous.
This has the added benefit of removing the dominant players ultimately coordinating the entire battle, playing everyone's guy...since without knowing the result it makes it difficult to optimize a strategy...Combat also typically go faster, as wasted action don't often need resolution, or mechanics can be all resulted quickly once everything is known.
The DM still has to "apply discretion", since like in the baseball diamond example, the net result of that would be either creatures converging toward the center with no one getting an AoO as well, or trying to get to first base...it really depends on how the last guy to act declared his action...whether they following the original companion at home base, or they literally wanted to move to 1st base.