pocketchange,
you haven't clarified as to the observation on the failed relay, i.e. whether it is the failure of the output relay or the failure of power supply module (capacitor etc.). I see you said there was a lot of smoke, is it from the electrolytic capacitor in the power supply module?
Further, the relay auxiliary power supplies are derived from the control power transformer of the MV contcator control scheme. If I guess right the control power for these contactors is 240V AC.
Now, if you consider the switchgear busbar voltage could be a bit above the normal rated voltage and there is a possibility that the control power transformer will have taps, putting things together, I see a possibility of the relay receiving more than 265V AC (if not, atleast working near its upper limit). Could you measure the voltage at the relay input terminals to check on this?
If you have to go ahead and replace all the relays, I see it is a big task and hence it is worthwhile to investigate little more so as to identify the cause and prevent further failres, if possible. Hope you would agree.