When should one implement cold-junction compensation in thermocouple applications?
... what sort of accuracy expectations demand cold-junction compensation as opposed to simple calibration?


An ideal thermocouple provides \$\mathrm{V_{out} = k \cdot (T_{hot}-T_{cold})}\$.

The end result cannot be more accurate than the accuracy to which you measure or infer the cold junction temperature, and in practice will be somewhat worse and can of course be much worse. 

Therefore, ALL thermocouple temperature measurements require cold junction "compensation".
 "Compensation" is really shorthand for "determining the temperature of the cold junction with a level of accuracy that is appropriate for the application". Compensation could consist of saying "this will be used in an air conditioned office which is temperature regulated to 20 degrees C - so that will be the cold junction temperature".