Carsten:
If you are powering the relay coil from the 3V supply then change your circuit. I would power the relay from the voltage that you have in front of your 3V regulator. Then drive the relay coil via a buffer of some sort such as DS2003 or an NPN transistor.

Also do not forget to install the free-wheel diode across the relay coil. This diode should be as close to the coil as possible.

If the noise is being injected into the GND then consider the same above steps if you are not already doing them. Then take a look at where the high voltage being switched is routed. Keep all the load leads away from the low voltage PC board leads.

Finally if it is impossible to isolate the relay from the micro to eliminate the spikes then try opto coupling the drive circuit to the coil. If you opto couple remember that it will be most useful if you route the coil side of the opto coupler circuit so that the coil current goes directly to/from the powersupply instead of through the power/gnd traces of the microcontroller board. Better yet use a separate power supply for the coil from the supply that powers the micro, if it is available.

Hope this helps
Michael Karas