Natural theorems proven only "to high probability"?
$
\DeclareMathOperator{\inv}{inv}
\DeclareMathOperator{\maj}{maj}
$
This is not an example of what you are asking for, but it suggests how such an example can come about. Some combinatorial identities can be encoded as identities about polynomials of bounded degree $d$. If the polynomials are univariate, to prove the identity it is enough to verify it on $d+1$ points. However, if the polynomials are multivariate, and the degree is at least moderately large, the Scwartz-Zippel lemma may be the only practical way to verify the identity.

For an example of the univariate case, check this article by Zeilberger, resolving a question of Knuth. He proves a statement about statistics of permutations. For a permutation $\pi \in S_n$, let $\inv(\pi)$ be the number $|\{(i, j): i &lt; j, \pi(i) &gt; \pi(j)\}|$ of inversions of $\pi$, and let the major index $\maj(\pi)$ of $\pi$  be the sum of all integers in the set $\{i: \pi(i+1) &lt; \pi(i)\}$ . Zeilberger proves that, for all $n$, the covariance of the two statistics is

$$
\mathbb{E}[(\inv(\pi) - \mathbb{E}[\inv(\pi)])\cdot(\maj(\pi) - \mathbb{E}[\maj(\pi)])] = \frac{1}{4}{n \choose 2},
$$
where all expectations are over a uniformly random $\pi$ in $S_n$. Zeilberger's proof is just a computer verification for $n \in \{1, 2, 3, 4, 5\}$, and an observation that the statement is equivalent to an identity between polynomials in $n$ of degree at most $4$.