Hmm...I don't see any real difference between this and an ordinary single-elimination tournament where the seeding is set from the start. Maybe I'm missing something.
Anyway, assuming that there isn't any difference, we observe that Player A has $2^n-1$ different possible opponents in the first round. Of those, $2^{n-1}$ are in the opposite half of the draw, and both they and Player A would have to win $n-1$ games to meet; this happens with probability $\frac{1}{4^{n-1}}$. $2^{n-2}$ are in the same half, but opposite quarters, and both they and Player A would have to win $n-2$ games to meet; this happens with probability $\frac{1}{4^{n-2}}$. And so on, until we get to the $2^{n-n} = 2^0 = 1$ single player who meets Player A in the first round. Altogether, the probability of Player A and a given Player B meeting eventually is
\begin{align}
\frac{1}{2^n-1} \sum_{k=1}^n 2^{n-k}\frac{1}{4^{n-k}}
& = \frac{1}{2^n-1} \sum_{k=1}^n \frac{1}{2^{n-k}} \\
& = \frac{1}{2^n-1} \sum_{k=0}^{n-1} \frac{1}{2^k} \\
& = \frac{1}{2^n-1} \left(2-\frac{1}{2^{n-1}}\right) \\
& = \frac{1}{2^n-1} \times \frac{2^n-1}{2^{n-1}} \\
& = \frac{1}{2^{n-1}}
\end{align}
I'll come back to edit this if I think (or someone points out) that there's a substantive difference between random reseeding and not reseeding.
There's also a pretty simple proof by induction: For $n = 1$ (two players), the probability is clearly $\frac{1}{2^n-1} = 1$. For $n > 1$, the probability that they meet in the first round is $\frac{1}{2^n-1}$. If they don't meet in the first round (with probability $\frac{2^n-2}{2^n-1}$), then they must both win their first games (with probability $\frac14$) to get to the next round. With reseeding, this is clearly the case of $n-1$, so with the premise that the probability of them meeting at that point is $\frac{1}{2^{n-1-1}} = \frac{1}{2^{n-2}}$, the overall probability for case $n$ is
\begin{align}
\frac{1}{2^n-1}+\frac{2^n-2}{2^n-1} \times \frac14 \times \frac{1}{2^{n-2}}
& = \frac{1}{2^n-1} \left(1+\frac{2^n-2}{2^n}\right) \\
& = \frac{1}{2^n-1} \times \frac{2^{n+1}-2}{2^n} \\
& = \frac{1}{2^n-1} \times \frac{2^n-1}{2^{n-1}} \\
& = \frac{1}{2^{n-1}}
\end{align}