Would this counterexample not be included in their search space?

They were looking at 16 variables, degree of about 10 in each one. That search space is simply too big for a plain bruteforce. So they did some sort of filtering to reduce the search space to a pool containing "possible counterexamples".

There was also a paper giving a lower bound of about 100 for possible counterexamples in that particular framework. Later raised to 108 in https://arxiv.org/abs/2204.14178

I don't remember the details very well since this was back in 2015 and wasn't really involved in the research. Consider this to be some sort of telephone game between what I heard in 2015 and what I remember today.

based on the approach described they were probably in dimension 2, this counterexample is 3 dimensional