First we tried with a 1000v 2.5a diode across the relay. (the cathode (white-banded) end is connected to the positive (red wire) terminal on the relay) Helped some but it still dropped out. It drops out less frequently at first, but the most noticeable change is that most of the buzz/hum is gone.
Then we added a ~0.6µf capacitor, made minimal difference.
Finally I've got the diode together with a 10µf capacitor (neg to neg if it's polarized) and it stays on.
(we're still going to try to find the cause next week, though)