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 [1].

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.

[1]: Practical Graph Isomorphism II, McKay, http://arxiv.org/pdf/1301.1493v1.pdf