The concept of "open-ended evolution" in artificial life is mostly misunderstood. In many cases, "open-ended" is taken to mean that the final solution can take any shape, however complicated. Instead, a stronger definition of "open-ended" would require that the fitness function itself is changing. For example, Genetic Programming would be defined as open-ended in the first sense, since the evolved programs can solve and computable problem (provided that the instruction set is Turing-complete), but is not in the second sense, as the programs are selected according to one, immutable fitness function. This is more akin to adaptation than evolution.
In my opinion, an important but neglected goal of ALife should be that of identifying a minimal set of conditions that is able to sustain this stronger kind of open-ended evolution.
What would it take for an artificial system to display "real" open-ended evolution? It is possible that there may be multiple answer to this question, but co-evolution of agents seems to be a good candidate. A minimal example might involve populations of agents trying to predict each other's output. The output of a population should be tied to the process of predicting the response of the others. To initiate a runaway evolution process, predicting a simple output should require a simple algorithm, which however would produce a slightly more complex output by the laws of the artificial world. In such a scenario, the fitness function is given by the combination of prediction algorithms in the population, and each evolutionary step changes it in a way that requires increasingly complex behaviors.