Suppose we sought to construct a consistent history of such a CA system by first starting with purely random values at each point in space and time. Now, obviously this arrangement will not satisfy the CA rules. But then we go through and start modifying things locally so as to satisfy the rules. We move around through the mesh in some pattern, repeatedly making small modifications so as to provide local obedience to the rules. Eventually, if we take enough time, we ought to reach a point where the entire system satisfies the specified rules.
Would this be guaranteed to work? You might get local regions of space and time that internally follow the rules but that are incompatible at their boundaries, like domains in a magnet. The algorithm would keep trying to modify things to make them globally consistent of course, but isn't it possible it'd get stuck in a loop?
Now, I'm not sure how to combine this process with Georges' proposal to maximize some criterion such as the gradient of orderliness. I suppose you could simply repeat this process many times, saving or remembering the best solution found so far.
As long as everything that happens in the universe's history can be represented by a finite string, this brute-force method is one that's guaranteed to work...the ultimate version of this would just be to generate all possible strings of that length, then throw out all the ones that don't match the laws/boundary conditions you've chosen. This method could also be used to generate histories satisfying global constraints that could be hard to simulate in a sequential way, like a universe where backwards time travel is possible but history must be completely self-consistent, where it is possible to influence the past but not to change it.
Find out everything you need to know about Las Vegas here for that getaway. http://special.msn.com/msnbc/vivalasvegas.armx