Do you have a diode back-biased across the relay terminals? Definitely necessary to dissipate the surge at turn off.
Also the relay may have more contact bounce than the membrane switch and its debounce circuitry. The circuit under test may be quickly cycling on off on off... half of the time ending up off!