The failure is probably due to high voltage transients generated when the solonoid coil is de-energised. The energy stored in the inductor's field is returned very quickly when power is removed and a high voltage reverse pulse is generated, (L di/dt). A pulse several hundred volts amplitude is not uncommon).
A capacitor across the output of the IC will not prevent this and may make it worse as it forms a parallel resonant circuit with the relay inductance causing ringing.
Place a reverse biased diode such as a 1N4004 across the relay coil, (located at the relay coil if this is practical), to absorb the reverse voltage spike, and now a capacitor across the output of the supply (eg 1uF 35V tantalum) would be of use to ensure the LM7812 is stable all the time.
The reason for locating the diode at the coil is one of good EMI/EMC control as absorbs the high voltage transient which also has a high frequency component, before it can be carried and radiated from the connecting wires.