Problems that are counter-intuitively solvable in practice? Recently, I went through the painful fun experience of informally explaining the concept of computational complexity to a young talented self-taught programmer, who never took a formal course in algorithms or complexity before. Not surprisingly, a lot of notions seemed strange at first but made sense with some examples (PTIME, intractability, uncomputability), while others seem to come more natural (problem classification via reductions, time and space as resources, asymptotic analysis). Everything was going great until I accidentally admitted that SAT can be solved efficiently* in practice... And just like that, I lost them. It didn't matter how convincingly I was trying to argue for theory, the kid was convinced that it was all artificial crap math that he should not care for. Well...

¯\_(ツ)_/¯

No, I was not heart-broken, nor did I really care about what he thought, that's not the point of this question. Our conversation had me thinking of a different question, 


  How much do I really know about problems that are theoretically
  intractable (superpolynomial time complexity) but practically
  solvable (via heuristics, approximations, SAT-solvers etc.)?


I realized, not much. I know that there are some very efficient SAT-solvers that solve enormous instances efficiently, that Simplex works great in practice, and maybe a few more problems or algorithms. Can you help me paint a more complete picture? Which well-known problems or even classes of problems are in this category? 

TL;DR: What are problems that are counter-intuitively solvable in practice? Is there an (updated) resource to read more? Do we have a characterization for them? And, finally, as a general discussion question, shouldn't we?

EDIT #1: In trying to answer my last discussion question about such a characterization, I was introduced to smoothed analysis of algorithms, a concept introduced by Daniel Spielman and Shang-Hua Teng in [1] that continuously interpolates between the worst-case and average-case analyses of algorithms. It is not exactly the characterization discussed above, but it captures the same concept, and I found it interesting.

[1] Spielman, Daniel A., and Shang-Hua Teng. "Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time." Journal of the ACM (JACM) 51, no. 3 (2004): 385-463.
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.