Try some resistance after the MOV (as much as you can tolerate, for acceptable losses at maximum load current).
Maybe even a second MOV after that.
Use bigger capacitors.
Current limiting devices (e.g., automotive load dump protection).
Crowbar type protection (thyristor type TVS, etc.).
Series fuse -- assuming it blows fast enough to matter, of course. (Even the fastest fuses take nearly a milisecond to open, so that's probably not helpful here. A fuse of any sort would be helpful to clear the fault and protect the wiring if a latching / thyristor type TVS is chosen.)
Series resistance helps by making a current divider. So, the first MOV soaks up almost all the current and clamps the voltage to a more reasonable value, then your circuit only has to deal with the ~70V or whatever. Which is still a lot more than 12V, but if you were to add another 2 ohms in series, you'd need to clamp only 30A, not 250A.
Note that a 20us time constant at 2 ohms suggests the test involves a charged 5uF capacitor; 100 times more, or ~500uF, will only be charged by 1/100th as much, or ~5V. Assuming the ESR is equally low: 1/100th of 2 ohms is 20 miliohms, which might be practical using aluminum polymer type caps. If you don't mind the price.
Correct, common mode doesn't matter here, and although you could filter the spike with inductance, it's not generally practical to do so. Example: suppose you want to absorb the 500V spike, rather than shunt it. It has a flux of about 5-10mWb, so for a current rise of say, 10A, that would require 500-1000uH, rated for saturation above 10A. 10A is certainly a lot more manageable, though still a lot of energy for an avalanche TVS to absorb (10A in 1mH is 50mJ, which -- maybe not too bad for an SMC size TVS, actually?). A thyristor type would be great here, given the limited dI/dt and transient filtering action resulting from the inductance. Or the dumb old MOV again.
Tim