I haven't seen any thorough analysis of how "hard" it would have been to find by brute force

Pretty hard. I asked Fable and it gave an estimate of 10^46 candidates in the counterexample's "reference class", and that's assuming you know how many distinct terms there are (as opposed to searching all polynomials of degree 7/6/4 for the three coordinates, which it estimates at 10^334).