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  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.
 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.