[JoshTriplett]

I found myself following a constraint-satisfaction approach to prune the search. I'd quickly work out the unrecoverable conditions to put constraints on the overall possible moves, then start thinking about possible states both forward from the start and backward from the solution, and consider the requirements to reach those states. That tends to produce new unrecoverable conditions and prune the search further.

Still, even with all of that, there was usually one particularly hard state to achieve that required some unusual step, and everything else mostly fell into place afterward.

[k_os]

You perfectly described my process so now there's 2 data points. If anyone else had some different way please share.

[anatoly]

Everything you said, plus - in the last levels I usually tried to find "the difficult thing" first. After looking at the push directions a bit, it becomes obvious that the difficult thing is going to be to position the red square, say. Then imagine possible solutions to the difficult thing, and go both forwards (after it's done the end is usually close) and backwards (how to set up the solution).