I had a problem with the demonstration in Permutation City. They claimed to chop up a simulated consciousness timewise, and then to run the pieces backwards: first the 10th second, then the 9th second, then the 8th, and so on. And of course the consciousness being simulated was not aware of the chopping.
The problem is that you can't calculate the 10th second without calculating the 9th second first. That's a fundamental property of our laws of physics and I suspect of consciousness as we know it. This means that what they actually did was to initially calculate seconds 1, 2, 3... in order, then to re-run them in the order 10, 9, 8.... And of course the consciousness wasn't aware of the re-runs. But it's not clear that from this you can draw Egan's strong conclusions about "dust". It's possible that the initial, sequential run was necessary for the consciousness to exist.
I doubt this is the case.
First of all, I don't think you should call it "law" at all, since such property is indeed derived purely from the interpretation we had made so far about our world. Although these interpretations (QM, Relativity, super string and etc.) are in favor now, they are logically no more "valid" than Newton's physics at his time (or even now). If we all this time dependency a "defect", then we (still) do not know whether it is a defect of theories we favored, or a defect of the world we are in now, or a defect of our reasoning ability, or even a resultant defect induced from some other defect of our world. Infinite (or at least very large) number of theory can be developed based on finite number of observed facts, just like infinite numer of curves can pass through finite number of common points. However, we have principles like Occam's Razor to choose between them. How do we know that some other theory may not suffer from this defect?
Second, even with the physics we use nowadays, there are still simple problems that can be calculate NOT IN ORDER. For instance, the displace of a single pendular at any time can be calculate regardless of its history. Put into more formal way, there exist some turing machine that can calculate in constant (regard to the time) steps. More generally, dynamic systems and complex systems are the only thing that has "history". However, many dynamic system can be translated (however messly) into simple system of equations that can be solved in constant time with some turing machine. Take gas for example, the position of each molecule is no doubt a hard problem that only expressed with dynamic system. However, if we are to talk about gas in a higher level in terms of volume, pressure, and temperature, then most problem can be expressed in simple systems that can be calculated in constant time.
Finally, our physics world may be one of the limit that some problem cannot be solved in constant time. This had been talked about quite thoroughly in the discussion about super-turing computation. I don't have much to add on to that.
Conclusion: A world can be simulated IN or OUT OF ORDER, depending on the physics to be simulated, the world the simulator is in, and the design of the simulator (which is related to the level of intellegence of the designer in this particular case).