There's also the problem of arcing across the relay contacts. I rarely work with relays, so I'm not up on this, but I did some googling and found that it's not a "easy" subject. It's called a "snubber", so Google "snubber for relay contacts" if you want to look into this.
Adding a snubber will prevent arcing on the relay contacts. This is important because arcing will chew up the contacts causing them to fail sooner than they should.
One "simple solution" I found, is to have two separate contacts (controlled by the same coil) in series. That widens the gap more quickly, supposedly preventing, or greatly reducing, the arcing. For this, you will need something like a double pole (or more) relay.
It was said, in another, reply, that the "diodes will stop arcing in the relays". If they were referring to arcing across the contact(s), this might not be correct. In one of the articles I read, a distinction was made between managing reverse EMF, and preventing contact arcing, and it was made clear that each needs a different solution.
If the contacts are visible, try watching the contacts while the relay switches [probably in a darkened room]. If you see arcing, even with the diode(s) in place, then you have your answer 