Problems that are counter-intuitively solvable in practice?
Highly structured SAT instances (even on millions of variables) can often be solved in practice. However, random SAT instances near the satisfiability threshold with even a few hundred variables are still open (meaning, even in practice, if you generate such a thing you may never know in the lifetime of the universe whether the thing you generated is satisfiable or not using current SAT solvers). You might be interested in this related question and its answers.
Clique finders are also shockingly good "in practice"


With respect to clique finders, (part of the) explanation is given
by an average case analisys of the algorithms in question.

See https://www.sciencedirect.com/science/article/pii/S0166218X18300167?via%3Dihub

Integer programming and mixed integer-linear programming (with some rational and some integer variables) are the focus of whole Operations Research departments, and can often (but not always) be solved in practice
From what I understand, many $\mathsf{PSPACE}$-complete problems that arise in verification can often be solved in practice, but "in practice" usually implies "on highly structured instances". (In contrast, we still don't know who wins for pretty small instances of the game of Go, which is another $\mathsf{PSPACE}$-complete problem.)
Many problems in computational algebraic geometry can be solved in practice on small instances using Grobner bases, but these fail miserably on larger instances, or even small instances that have high "complexity" (as measured by the Castelnuovo-Mumford regularity). And these problems are even $\mathsf{EXPSPACE}$-complete!
As already pointed out in the comments by D. W., Graph Isomorphism can pretty much be solved in practice. It is very hard to stump modern GI software such as nauty, bliss, saucy, etc.