My two yen on the subject;
I had an IDENTICAL problem waaay back.
What happens is that as the relay contacts open or close there is contact bounce. The resultant arcing creates an incredibly wide noise spectrum. Unfortunately, the relay's coil acts as a pickup coil (much like a pickup coil in an electric guitar) for the resultant noise which is fed back to the circuit.
Sometimes the noise pulse is so severe that defies almost any decoupling efforts.
How did I solve the problem back then? Use an optocoupler to drive the relay. To avoid having a separate, isolated supply only for energizing the relay's coil, use an AC-coil relay and drive it with a Triac-output optocoupler.
Worked great for me.