You are right. The Auslander-Buchsbaum-Serre theorem implies that the projective dimension of a CM module over a regular local ring is $0$ and hence a CM sheaf over a regular scheme is locally free.
It is quite easy to give examples of non-locally free CM sheaves.
It is relatively easy to prove that if $X$ is CM, then $\omega_X$ is a CM sheaf.
So, take any $X$ that is CM, but not Gorenstein. Then $\omega_X$ will be a non-locally free CM sheaf. Here is an explicit example:
$$X=\mathbb A^3/(x,y,z)\sim (-x,-y,-z)$$
See this MO answer for a proof that $\omega_X$ is not locally free. The fact that this $X$ is CM follows from that it is a finite quotient.
Let $X$ be a normal surface (hence it is CM) and $\mathscr F$ an arbitrary reflexive sheaf of rank $1$. Reflexive sheaves are $S_2$ and hence on a surface CM, but they're not always locally free. In fact, these sheaves correspond to Weil divisors while locally free sheaves of rank $1$ correspond to Cartier divisors.
So for these sheaves there is a criterion you are looking for:
A reflexive sheaf of rank $1$ (which is CM on a normal surface) is locally free if and only if the associated Weil divisor is Cartier.
I don't know if there is an elegant criterion for a CM sheaf to be locally free. There is one result that is sometimes useful:
Let $f:X\to Y$ be a morphism with equidimensional fibers. If $Y$ is regular and $X$ is CM, then $f$ is flat.
In particular, if $f$ is finite, then $f_*\mathscr O_X$ is locally free.