In what cases should plasmas be considered compressible?

Thus, more generally, when should incompressibility be approximately valid (e.g. fluid flow is much smaller than sound speed)?

The only time this is really assumed is if the process occurs very slowly compared to the relevant communication time scale, e.g., transit time of a sound wave. It's similar to neutral fluids where, for instance, in situations when the flow speed is well below the sound speed it is valid to treat the fluid as incompressible. However, very few things in space plasmas actually qualify as incompressible.

I was listening to a lecture where it was mentioned incompressibility was assumed during derivation of an electrostatic instability, but incompressibility was not assumed for an electromagnetic instability.

This seems a little backwards to me. If you examine the derivation of an electrostatic ion acoustic wave, for instance, in a two-fluid approximation you will find that compressibility is required. I am guessing the speaker was discussing some extremely low frequency approximations in this context, namely waves in a special MHD limit? Even so, the slow mode (i.e., the low frequency extension of the ion acoustic wave) and fast mode fluctuations are compressible.

As an aside, many turbulence theorists will assume incompressibility for the sake of tractibility in solving equations analytically and this is okay under certain limits similar to how it is okay to approximate the plasma as being cold under under certain limits. However, it is not a generally true approximation to say that the plasma is incompressible as this is very rarely true.