Plenty of NP-complete problems have easy instances. Indeed for a lot of problems there's an assumption that most instances that naturally arise are easier and well solved by heuristics but there are some pathological instances that aren't but don't appear in practice

Also: if you are okay with heuristics that aren't guaranteed to output the optimal answer the whole point is moot