I asked a similar question here: Permutation search problems with no known $o(n!)$ algorithms; to which one-way functions over a space of permutations gives a problem with no $o(n!)$ solution (discussed in the comments).
I am now asking for a more natural permutation search problem with no efficient solution in practice.
An example where this is not the case is the graph isomorphism problem, which has no known polynomial time solution, but backtrack search can perform very well on all known classes of graphs .
Therefore, I am wondering if there are other permutation search problems that are either considered intractable in practice, or whose backtracking heuristics have known classes of problems in which they perform very poorly.
: Practical Graph Isomorphism II, McKay, http://arxiv.org/pdf/1301.1493v1.pdf