Counterexamples can be decidable and arbitrarily ugly or difficult to find. If you know anything about mathematics it's trivially simple things can yield extremely complex structures. And that can absolutely include terse conjectures whose solutions are in fact decidable but only with proofs that would consume more than a bit of memory for every particle in the universe. Not logically undecidable, but physically impossible to prove in our physical universe.

Further down the scale are ones that are decidable only by machines that we would never have the wherewithal to construct, even though they could physically be constructed with the material we have to work with.