Ok, I had a chat with my father, who is an old engineer and used to work in BT in the 50's, he told me of a trick they had back then. Apparently they let the relay weld and would "unstick" it, and do this a few times. He claims this would even out the surface and create a bigger surface of contact so less micro-welding.
Well, I tried this, and after 5 or 6 times the relays no longer locked!
All is well now