Are there any heuristic-free NP complete problems?
See Josh Grochow's answer to Poly time superset of NP complete language with infinitely many strings excluded from it. According to that answer, under some natural cryptographic assumptions, for every co-NP-complete problem there is an infinite subset $\Phi$ of instances such that membership in $\Phi$ is polynomial time, and the decision problem restricted to $\Phi$ is trivial (answer always no).

This can be formalized by stating that no co-NP-complete set is P-immune. It is also known (again under cryptographic assumptions) that no NP-complete set is P-immune. So there is another infinite subset $\Phi'$ such that membership in $\Phi'$ is polynomial-time testable and the decision problem restricted to $\Phi'$ always has answer yes. See e.g. Glasser et al., "Properties of NP-Complete Sets", SICOMP 2006, doi:10.1137/S009753970444421X.