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.