This is not an answer, but only an attempt to remove the "mind-boggling" aspect of the problem. 

As in the OP, let $S_n$ denote the set of all permutations of the set $[n]:=\{1,\dots,n\}$. Let $P_n$ denote the set of subsets of $[n]$ of cardinality $2$. 

For any permutation $\pi\in S_n$ and any "unordered pair" $p\in P_n$, let 
$$\tau_\pi(p):=\min\{i\in[n]\colon\pi(i)\in p\}. $$
Also, any permutation $\pi\in S_n$, which we can think of as a re-labeling of the elements of the set $[n]$, induces the permutation/re-labeling (which we will denote also by $\pi$) of the set $P_n$ by the formula $\pi(p):=\{\pi(i)\colon i\in p\}$ for $p\in P_n$. 

Take any permutations $\pi$ and $\rho$ in $S_n$. We are comparing the families $\tau_\pi=(\tau_\pi(p))_{p\in P_n}$ and $\tau_\rho=(\tau_\rho(p))_{p\in P_n}$ (that is, the functions $\tau_\pi$ and $\tau_\rho$ from $P_n$ to $[n]$), by considering (say) the difference
$$d(\pi,\rho):=\sum_{p\in P_n}1(\tau_\pi(p)<\tau_\rho(p))-\sum_{p\in P_n}1(\tau_\pi(p)>\tau_\rho(p)).$$
Note that $\tau_\pi(\pi(p))=\tau_\rho(\rho(p))$ for all $p\in P_n$ or, equivalently, $\tau_\rho(p)=\tau_\pi(\pi(\rho^{-1}(p)))$ for all $p\in P_n$; that is, $\tau_\rho=\tau_\pi\circ\pi\circ\rho^{-1}$. So, the family $\tau_\rho$ is obtained from the family $\tau_\pi$ by applying the permutation/re-labeling $\pi\circ\rho^{-1}$ to the index set $P_n$ of the "unordered pairs". 

So, there is no reason to expect that 
$\tau_\rho=\tau_\pi$ in general, and hence there is actually no reason to expect that $d(\pi,\rho)=0$ for arbitrary permutations/re-labelings $\pi$ and $\rho$ in $S_n$.