Let $X$ be a complete metric space. Suppose a sequence of elements $x_n$ is Cauchy in mean, in the sense that
$$\lim_{K \to \infty} \limsup_{N, M \to \infty} \frac{1}{NM} \sum_{i = K+1}^{K + N} \sum_{j = K+1}^{K + M} d(x_i, x_j) = 0.$$
Is it true that $x_n$ admits a convergent subsequence?
The answer is yes. This solution was provided to us by Reddit user Ravinex.
The trick here is that we need to treat $N$ and $M$ independent. It turns out that it's not true if we only have $N=M$ in the limit (Choose $x_i$ to be equal to $a_i$ on on $[0,1]$ and $0$ otherwise where $a_i$ is extremely slowly growing: then the majority of the average is contained on a large set where $x_i$ is essentially constant in $i$).
The key idea is the following. Fix $a > 0$. Then by assumption, if $K$ and $R$ are large enough, then if $M > R$ and $N > R$, the average value of $d(x_i, x_j)$ where $K+1 \leq i \leq K+N$ and $K+1 \leq j \leq K+M$ is at most a. In particular, at most a fraction $\sqrt a$ of all possible pairs can be bigger than $\sqrt a$ (otherwise the average would be at least $a$). Now, if $N/M < \sqrt a$, only a fraction $\sqrt a$ of pairs $i,j$ happen when $j \leq K+N$. Thus, at most $2 \sqrt a$ fraction of pairs $i, j$ have either $d(x_i, x_j) > \sqrt a$ or $K+1 \leq j \leq K+N$.
In particular, there are at least $(1-2\sqrt a)MN$ pairs $i,j$ with $d(x_i, x_j) < \sqrt a$ and $K+1 \leq i \leq K+N$ and $K+N \leq j \leq K+M$. Thus a fraction $\frac{1-2 \sqrt a M}{M-N} \geq (1-2 \sqrt a) \geq 1-2 \sqrt a$ pairs in $[K+1,K+N] \times [K+N,K+M]$ satisfy $d(x_i, x_j) < \sqrt a$. In particular, I have constructed a "short-by-long" rectangle where with the vast majority of pairs have small difference. Now we can iterate this.
Let's define $K_i,N_i,M_i,R_i$ inductively, as follows. Choose $K_1$ large so that if $R_1$ is large enough and $M,N > R_1$, the average value of $d(x_i, x_j)$ over $K_{1+1} \leq i \leq K_{1+N}$ and $K_{1+1} \leq j \leq K_{1+M}$ is at most $a_1 = \frac{1}{100}$. Now choose $K_2>K_1$ large enough similarly, but so that the average is at most $a_2 = \frac{1}{100^2}$. Increasing $K_2$, we may assume that $K_2 >> K_1+R_1$, so define $N_1$ via $K_2 + 1 = K_1 + N_1$. Now choose $K_3$ and $N_2$ similarly. Define $M_1$ so that $K_2 + N_2 = K_1+M_1$. Increasing $N_2$ (and hence $K_3$), we may assume that $\frac{N_1}{M_1} < \sqrt a_1$.
Now keep going in this fashion.
Thus, by the key observation, we have that for $K_r + 1 \leq i \leq K_r + N_r$ and $K_r + 1 \leq j \leq K_r + M_r$ the average of $d(x_i, x_j)$ is at most $a_r = \frac{1}{100^r}$, and moreover that $\frac{N_r}{M_r}$ is at most $\sqrt a_r$. From our observation, we know that at least $1-3 \sqrt a_r$ of pairs $i,j$ in $[K_r+1,K_r+N_{r}] \times[K_r+N_r,K_r+M_{r}]$ satisfy $d(x_i, x_j) < \sqrt a_r = 1/10^r$.
Now choose $i_r$ uniformly at random over $K_r + 1,...,K_r + N_{r}$. I claim that with nonzero probability, $d(x_{i_r}, x_{i_{r+1}}) < \sqrt a_r = \frac{1}{10^r}$ which is enough for $x_{i_r}$ to be a Cauchy subsequence.
By the convenient construction $K_{r+1} + 1 = K_r + N_{r}$ and $K_{r+1} + N_{r+1} = K_r + M_r$, and so $(i_r, i_{r+1})$ is actually uniform over $K_r + 1 \leq i_r \leq K_r + N_{r}, K_r + N_{r} \leq i_{r+1} \leq K_r + M_r$. So the probability that $d(x_{i_r},x_{i_{r+1}}) > \sqrt a_r$ is at most $2 \sqrt a_r$. So the probability that at least one pair $(i_r,i_{r+1})$ is bad is at most the sum of these, i.e. $\frac{3}{9}$.
Thus, the probability that the randomly chosen sequence is Cauchy is $\frac{7}{9} > 0$, and so $x_i$ admits a convergent subsequence, as claimed.
