I have an engineering background and this is an interesting problem, so I thought that I would chime in 
It sounds like arcing is causing the relay contacts to stick together in the closed position regardless of the relay actuator. The root cause of the problem may be that the contacts are made of some soft/easily melted material, which inherently makes that material a poor choice for use as relay contacts. Simply put, the root cause of the problem may be poor design of the relay.
The power supply may be a contributing factor as it may have a high inrush current that significantly exceeds the design of the relay. I don’t know what kind of power supply is being used for this, but high inrush current is a characteristic of conventional, non-switching type power supplies. Correctly-size switching power supplies should not have the same problem or at least not to the same degree. A properly-sized resistor placed in series with the power supply should help reduce in-rush current.
The power supply design may also have some reactive/inductive design that causes an arc when the contacts open. This particular issue is characteristic of conventional non-switching power supplies that have a transformer primary wired across the mains. A disk capacitor placed across between the two relay contacts should suppress arcing when the contacts open. Adding a gas tube in parallel with the capacitor would also help. Gas tubes are fairly slow to ionize, so the capacitor would be mandatory and the gas tube would just provide additional suppression.
Rather than analyze and experiment, it might be better to eliminate the problem by adding a Solid State Relay (see Solid-state relay - Wikipedia). Use the Fibaro relay contacts to send mains voltage to control the SSR and let the SSR do the heavy lifting to start/stop the power supply. SSRs have an inherent advantage in that when they switch mode (on to off or vice versa), they do so during the mains sine wave zero crossing point. At the zero crossing, there is zero voltage and current available on the mains and so there is no current in-rush or high-voltage inductive arc possible.
SSRs are relatively cheap and effective. Additionally, it should be easy to retrofit to the existing configuration - at least for testing and experimentation purposes.
Ken