Try a snubber across the contacts, say 0.01uF 250V + 47 ohm.
While it may be that your power rail really is that sloppy, I suspect you will find that you measure the same transients even when probing ground to ground. That is, if you clip the probe tip to ground clip, and probe around with that, you will find the same signal on GND in most locations in the circuit, and the same signal on +5V in most locations in the circuit (assuming your circuit and oscilloscope are isolated of course, so it is safe to connect probe ground to +5V).
This occurs because common mode noise is coupled into the circuit from the contacts opening. You need to provide an alternate path for that current to flow, or to dampen the voltage in the first place, that's causing that current to flow.
Tim