HugoPT:
My fix is to put a polyester cap in parallel to the relay.
The problem with that, is that you now have a huge surge current when you try to turn the relay on, which is of equal or greater magnitude to that on switch-off.
Note that a "snubber" diode very effectively limits the kickback voltage from the relay, but the current (inductive) transient appears in the circuit loop comprising the diode, the switch transistor, and the power supply, so the diode needs to be located adjacent to the transistor and not at the relay, and you need your decoupling capacitor here as well. Driver ICs containing the snubber diodes are well designed in this respect.