I'd loosen the problem a bit myself. After all, the Mona Lisa isn't a solid block of black either. It should be possible to put down a stipple pattern that, by construction, isn't a Garden of Eden pattern for at least one generation. This gives some degrees of freedom in the output. This should make the problem mathematically more tractable, although computationally more difficult since now we're searching a large space rather than being able to pretty quickly just go "nope, no solution".
How far back you could push that, I don't know. One generation before is almost certainly going to look very like the final picture. The "real goal" is almost certainly to get something that doesn't look much like the original for as long as possible, only for it to flash into existence with as little warning as possible. Though you could augment the scheme I describe above by coloring in the large chunk of non-alive spaces with patterns that fully extinguish themselves, which would at least somewhat obscure those portions.