If Let $ \mathbb{P}_{lm}$;  $l,m \in \{1,\ldots, M\}$ be the $(n-1)$-dimensional space consisting of points satisfying $v^T(\mathbf{X}_l-\mathbf{X}_m) = 0$ Then as long as $\mathbf{X}_l-\mathbf{X}_m$ is nonzero the probability that a randomly chosen vector of norm 1 from ${\mathbb{R}}_n$ lands in $\mathbb{P}_{lm}$ is 0 (as it would be for any $(n-1)$-dimensional space).

So let $A$ be the randomly chosen matrix from $SO_3$. For any positive integers $l,m \le M$ and $p \le n$ only way $A\mathbf{X}_l$ and $A\mathbf{X}_m$ can agree on the $p$-th coordinate is if the $p$-th row $v_p$ of $A$ is in $\mathbb{P}_{lm}$. Given $A$ randomly chosen from $SO_3$ and any one such integer $p$, the vector $v_p$ is chosen according to the uniform distribution from the set of vectors of norm 1. The probability of $v_p$ being such is 0. So finish using the Union Bound.

*By randomly chosen we mean that each coordinate of $v$ is picked independently of one another according to the uniform distribution on $[0,1]$. In fact each coordinate of $v$ could be picked according to any continuous distribution