If you want to use the C-element in arbitration / asynchronous logic, then a so-called MrGo circuit - a Seitz arbiter with an anti-metastable element - is a much more robust solution. All async arbitration relay logic needs anti-metastable elements, otherwise it's glitchy exactly as you describe.
Below is a tested 2-input Seitz arbiter design for armature relays. Diode snubbing is not recommended, since it slows everything down. R-C snubbing is the way to go. On low-voltage relays, the external resistor may be necessary. On most relays, though, the internal coil resistance provides all the attenuation needed, and only an external capacitor across the coil is needed.
There are three copies of this circuit on a card with 36 edge connector terminals - thus the STOP contact outputs are paralleled, as there wouldn't be enough pins otherwise :)
I've ran this circuit for about 200E6 cycles at 50Hz using 3-decade-old NOS Japanese armature relays whose contact life was rated only for 1E6 operations. It ran without mis-arbitrations throughout the entire test. Eventually I just got tired of the buzzing and turned the test bench off. For all I know, these things would last a billion cycles.
The particular relays I'm using are 3V, 0.5W coil models, last made two decades ago. These are not amenable to "capacitor based" solutions. I've tried: the necessary capacitors run into millifarads. The coil resistance is 18 ohms... It will work fine on higher coil voltage (and coil resistance!) relays of course - just adjust the snubber values and LED dropper resistors.
The design of the arbiter is a reimplementation from CMOS after Marly Rocken & al., after Seitz's arbiter.
The first request to come in "wins", and gets granted. While either request is active, if another request comes in, it gets deferred until the original request is removed.
When two requests arrive at once, one gets granted, but it's indeterminate which one. In practical terms with relays, the initial behavior favors one side when both requests are driven from the same source. Eventually, as the relays get hot, both sides of the circuit start to balance out in terms of speed, and the grant selection becomes chaotic/random.
I'm using this one in a larger design of an asynchronous relay computer, where it is used to condition all asynchronous external inputs, such as clock stopping, front panel toggles and test and debug (per Marly Roncken, Swetha Mettala Gilla & al.).
It is a robust and dependable circuit. An NMOS-like reimplementation that uses fast SPST NO reed relays arbitrates coincidental requests in about 300us worst case :)