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.

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

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).

Got all 35 - I did brute forcing with a few rules:

1) Don't worry about the colors at all, because you can usually shuffle them around to get the right order.

2) If there's a particularly cute combo, it's probably part of the solution.

3) Work out the most likely last few moves, going backwards from a winning position.

I never finished the book, but I'm reminded of Malcom Gladwell's Blink whenever I have moments of subconscious problem solving. It's a strange feeling: insight followed by a confused determination as a my conscious mind pieces together what the sub figured out.