It's worth noting this cuts both ways. An NP-complete problem may wind-up having only a few instances that are exponential in the inputs but a problem that is "only" O(input-size^3) is going to be difficult to deal for input of significant size.

Like matrix multiplication! That's N^3 naively. If you take N to be the size of each dimension.