I guess I've never thought of search as being either connectionist or non-connectionist. It's self-evident that people search (eg look up in books) things that aren't in local memory.

I think the distinction is how the looked-up knowledge is integrated.

The non-connectionist, classical, symbolical aspect is not so much "search" per se, but the fact that MCTS performs a form of look-ahead, which requires manually encoding the rules of the game in some fashion.

Determining what the legal moves in a state are, and what state results from a given move, is not something the AI would learn by itself, but is programmed into the system by a human expert.

I do not believe this is still true in MuZero, where no rules are ever explicitly encoded, beyond what leaks in from the reward function?

Indeed, in this latest iteration the network learns a model of the game by itself. Note however that it still uses MCTS and performs a look-ahead, i.e. it is still being "told" by the programmers how to do search (planning), only now it is left to the system to determine how it wants to represent states/actions/policies internally.