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$.
Below is an illustration, in Mathematica, of what has been said above:
