See EDIT section below for what I now think is happening
Maybe consider a zener diode in series with a normal diode to return excessive energy to the 24 volt positive rail. This would be needed for both halves of the bridge. I'm not sure if 5 watt zeners will be "man enough" because the pulse width is not stated. Longer pulse widths of the rogue transisent means more power dissipated in the zener.
The resistor and relay is a good idea but I might be concerned about heavier loads causing the same problem. An RC snubber in conjunction with the zener might also be a good idea too.
If you have a simulation tool that can adequately demonstrate the problem then I'd consider using it for trialling ideas.
Are you also sure it isn't a core saturation issue at starting up? This can be quite common. Maybe a bit of C9 and saturation?
EDITED from here onwards:-
If you are seeing large spikes on the MOSFETs then, I believe, that is not a problem associated with the load current - the MOSFET's inbuilt diodes should "shunt" excessive voltage back to the power rail V\$_{BATT}\$. Why are they not doing this? "Are the spikes really there" is my first question. Oscilloscopes are notorious at picking up spikes when measuring SMPSUs - the scope ground connection has to be very close to the measurement point or the large currents in the local circuit can induce "false" voltages into the probe/earth wire combination.
If the spikes are really present, then the MOSFET's parasitic diodes should catch them. Obviously you have to check that the parasitic diodes can handle this current. You also have to ensure that really good supply decoupling is present right at the points where V\$_{BATT}\$ meets the FET sources. Ditto on the GND nodes close to the other FETs. Without good decoupling at these points, the trace inductance can allow these spikes to be high enough to destroy the MOSFETs. I don't think you can rely on the 4700uF caps shown in the circuit. These are likely to have significant parasitic inductance due to their physical size.
Here's a picture I drew in case it wasn't clear. At the bottom of the picture is what I believe to be the more likely cause: -

When the switching circuit is running normally you'd expect the primary inductor current to have an average value of zero amps i.e. it might ramp up to 10A and ramp down to -10A BUT, at start-up this is never the case - the current has to begin at zero amps and during the first few cycles it could be the largest current that the MOSFET will ever encounter. This, if not correctly accounted for, WILL cause the core to saturate. Having a large load at power-up doesn't make saturation any worse but it will add to the excessive current seen by the MOSFETs.
What happens when the core saturates? Well, before saturation the current might be rising at (say) 1 amp per microsecond. During and through saturation this "rate" might double or triple and it is this peak excessive current that I believe is killing the MOSFETs.
The core can be prevented from saturating by adding a small air-gap - this might mean more turns to return the primary inductance to the design aim BUT, the net effect (even after adding those turns) is the the magneto-motive force (ampere-turns) will be smaller. Remember inducatcne rises as turns-squared; MMF rises proportional to turns.
Another method is to run the oscillator at a higher speed during start up - this shortens the "charge" time of the primary inductance and the current can be "made" to not reach saturation - this is only needed for a few milli-seconds but is worth considering as an alternative to redesigning the core/turns.