When is a blow-up Cohen-Macaulay?

The local complete intersection case is actually straightforward:

Claim Let $X$ be CM and $Z$ an lci subscheme. Then $Bl_ZX$, the blow-up of $X$ along $Z$ is also CM.

Proof: Let $\pi:Bl_ZX\to X$ denote the blow-up. Clearly, $X\setminus \pi^{-1}Z\simeq X\setminus Z$ is CM. Since $X$ is CM, so is $Z$. Since $\mathscr I$, the ideal sheaf of $Z$ is locally generated by a regular sequence, the sheaf of rings $\oplus \mathscr I^n/\mathscr I^{n+1}$ is locally a polynomial ring and hence $E=\pi^{-1}Z\to Z$ is a $\mathbb P^r$-bundle where $r={\rm codim}_X Z-1$. Since $Z$ is CM, so is $E$. Finally, since $E$ is a Cartier divisor which is CM, so is $Bl_ZX$ along $E$. $\square$

(For more on this see $\S$5 of this paper.)

Since Cohen-Macauleyness is a local property, we can restrict ourselves to the affine case.

So, let $R$ be a Noetherian ring, $I \subset R$ be an ideal and let us consider the so called Rees algebra

$\mathcal{R}:= \oplus_{n=0}^{\infty} I^n=R[It]\subset R[t]$,

together with the associated graded ring

$\mathcal{G}:=\mathcal{R}/I \mathcal{R}$.

Then $\textrm{Proj}(\mathcal{R})$ is the blow-up of $\textrm{Spec}(R)$ along $V(I)$, and the exceptional divisor is $\textrm{Proj}(\mathcal{G})$.

Then your question is closely related to the following:

When is $\mathcal{R}$ Cohen-Macauley?

This problem was studied by several authors and there are many results. See for instance the paper

Necessary and sufficient conditions for the Cohen-macauleyness of blow-up algebras by Polini and Ulrich and the references given there.

Here's a slightly different idea for references.

See On Macaulayfication of Noetherian schemes by Takesi Kawasaki. In particular, Theorem 4.1 gives a criterion for when blow-ups of certain ideals are Cohen-Macaulay.

Macaulayfication is a way of blowing up an ideal on a scheme and obtaining a Cohen-Macaulay scheme. Macaulayfications always exist, even in mixed characteristic, as long as a dualizing complex exists.

The point of Theorem 4.1 is that when you blow-up various things (generated mostly be regular sequences, in other words maybe even close to the the complete intersections you mentioned), you still get a Cohen-Macaulay scheme. If your ambient scheme is already Cohen-Macaulay (for example smooth), then you have a lot more flexibility in how you can choose these parameters, whichwhich sounds potentially useful to you.

I should point out that this may not work at all (ie, nothing interesting may result), it's just an idea.