If Let $P_{lm}$; $l,m \in \{1,\ldots, M\}$ be the $(n-1)$-dimensional space consisting of points satisfying $v^T(X_l-X_m) = 0$ Then as long as $X_l-X_m$ is nonzero the probability that a randomly chosen vector from ${\mathbb{R}}_n$ lands in $P_{lm}$ is 0 (as it would be for any $(n-1)$-dimensional space).
So let $A$ be the randomly chosen matrix. For any positive integers $l,m \le M$ and $p \le n$ only way $AX_l$ and $AX_m$ can agree on the $p$-th coordinate is if the $p$-th row of $A$ which was randomly chosen is in $P_{lm}$. The probability of this happening is 0. So finish using the Union Bound.