Do you have any counterexamples which aren't finite games where all the potential moves and outcomes can (at least in theory) be exhaustively enumerated at any point in time?
You can approximate most everything in theory almost perfectly by a set of very large but finite moves. Driving a car can be approximated as a set of finite moves (ie: 0.001 degree changes in wheel position) done at finite intervals (say 10000 "frames" per second). That'd give you more precision and a finer time grain than even a human brain is capable of.
And you don't need a 'very large' set of moves in the first place. 100 wheel positions are enough to give you 1-degree accuracy near neutral, and moderate but sufficient accuracy for strong turns. If you're looking at a delta from the previous position, 30 will do the job. Multiply that by 10 to 40 positions for the pedals, run the whole thing at 20Hz, and you're good to go.
kjksf did give an example: Go. The state space there is much larger than could ever be enumerated before the heat death of the universe.
That's why I said "at least in theory." The fact remains that everything theoretically possible in Go is known ahead of time, and furthermore it is trivial to generate training data and run simulations to improve the algorithm without putting human lives at risk.