Dear Hoffmann
I have experienced exactly the same problem in one of my design.Even when there was no AC load it was giving noise to my system.You MUST use an ULTRA FAST diode across the relay coils and ACROSS THE RELAY CONTACTS YOU PUT A SERIES COMBINATION OF 0.47Uf/400V CAPACITOR AND 47 OHM/0.5 WATT RESISTOR.This RC combination is for a maximum load of200-500mA @ AC 250V.
And the suggestion of Anil Guptha is appreciable and will help you at worst noise conditions.
better luck
Saji