Any problems/games/puzzles in which exhaustive search cannot show that a solution does not exist?
This should be a comment, but I don't have enough reputation to comment. I will remove this answer if question is updated

Your question is not really clear. As I understand it, the definition itself of the exhaustive search show that it's always possible to determine if a solution is valid or not.

Exhaustive search is defined as :


For a given potential solution, can determine if this solution resolve the problem.
Test every possible potential solution


From this, there is no problem where every potential solution is tested, but the search cannot show that a solution exist : either it exist and the search found the candidate, or it does not exist because all possible candidates were tested.



Maybe what you meant when asking your question is : "Any problems in which exhaustive search cannot be applied ?"

And the answer is yes, there is plenty of problems where the search space is way to big to be integrally searched : for example the Rubik's cube 3*3*3 has 43 252 003 274 489 856 000 combinations (source).

My answer need more source, specifically about the exhaustive search definition. I would be happy to add it if you could share :)