Another problem with NP-hard is that it only covers deterministic algorithms.

Even if most instances of a problem are deterministically hard, they might still have a randomized algorithm which solves them feasibly.