A friend and I were thinking about this problem today but we were unable to come up with a solution.
Problem:
Consider the the numbers $S=\{1,\ldots,n\}$. Given $2\le d \le n$ what is the maximal number of permutations $p(d)$ of $S$ you can choose such that the following holds: Whenever you compare two chosen permutations, they differ in at least $d$ spots?
Note that we always have $2\le d\le n$ since two permutations cannot differ in exactly one spot.
Note also that $n\le p(d)\le n!$ for all $d:$ $p$ is non-increasing and for $d=n$ one can choose the natural order first and proceed cyclically by writing \begin{matrix} 1 & 2 & \ldots & n-1 & n \\ 2 & 3 & \ldots & n & 1 \\ \ldots & \ldots & \ldots & \ldots & \ldots \\ n & 1 & \ldots & n-2 & n-1 \\ \end{matrix} so that $p(n) \ge n.$ Actually $p(n)=n$ since when writing the $n$ permutations differing in $n$ spots in pairwise comparisons into the rows of a matrix, the first column will contain all $n$ numbers. Thus it is not possible to add a row to the matrix that differs from all previous rows at the first index.
Example: for $n=3$ all possible permutations are: \begin{matrix} 1 & 2 & 3\\ 1 & 3 & 2\\ 2 & 1 & 3\\ 2 & 3 & 1\\ 3 & 1 & 2\\ 3 & 2 & 1 \end{matrix} For $d=3$ we get $p(d) = 3$ since $n=3,$ by the reasoning outlines above, and for $d=2$ we get $p(d) = 6$ since all distinct permutations differ in at least two spots.
You are looking for size of permutation code with Hamming distance. I have found a two years old survey of it - http://www.math.uvic.ca/~dukes/pc-talk.pdf. Most problems are open - for example, even sizes for $n = 7, d = 4$ and $n = 7, d = 5$ are unknown.