Geoff,
I'm the consumate newbie on the CNC end of this subject, having just joined because I decided to convert my electrically driven manual lathe and mill (mini asian varieties).
I, do, however have a long history with welding and cutting equipment.
Some plasma machines establish and quench the arc by moving the gun electrodes apart with the plasma feed gas (air in most machines). The shutdown switch closes the air valve, which allows the arc electrodes to fall back together (they're spring loaded), thus opening the contactor. If your machine uses this system (Hypertherm does at least in some of their machines - I have one), then there is a delay while the pressurized air lines past the valve bleed down thru the nozzle. during this time the plasma flow continues. It's unnoticable in manual operation unless you are aware of it.
This might be what is happening, and close observation of the shut-down should determine if it's the problem. If so, minimizing the pressure and volume of the lines past the solenoid valve will help. You my be able to wire the contactor so your CNC relay opens the contactor directly, but that may interfere with the arc establishment sequence. A different nozzle spring may help too, but I'm just guessing there. The plasma cutter manufacturer couls say for sure.
If not, sorry to waste your time. I'm sure these guys will help you solve it.
Scott