If a genetic algorithm were used to search it seems like the fitness function is obvious (it moves across for ever two moves up using a minimum number of iterations), but the mating function is not obvious. So I'm wondering if it's a brute force sort of search.
I've done a lot of work with GAs, and they've got a place, but ironically Life is not where they belong. Apparently they're using SAT solvers for the search, which is a lot more reasonable. The problem is exactly as you state it -- there's no fitness function that can take you from infeasibility to feasibility.
A combination could be interesting - SAT to smooth the space for a GA search.
Yeah, a lot of the original work on how GAs would optimize NP-complete problems is pure hand-waving and wishful thinking. Building-block theory, schema processing, it all sounds nice, but tends to result in disappointment. The thing GAs are actually good at is population-based search -- maintaining a bunch of alternative ideas at once. Either your suggestion of using GAs as a local optimizer for the non-satisfiability part of a mixed problem, or the inverse, using the GA to suggest starting points and using a SAT solver for the local search, is much more likely to produce interesting results. It's an idea I keep coming back to, although I still haven't struck gold with it.
Genetic algorithms tend to not work very well when the overwhelming majority of points in your search space have a fitness of zero.
People have tried to use genetic algorithms to search for patterns in Life, but have been unsuccessful because the evolution of a pattern is very sensitive to initial conditions.