I don’t have a solution because I have not experienced the problem, but I do have some questions.
What version of PHP is running on the servers where the relationship is not saving?
Do you have an issue with other field types that save serialized data, for example multis select, taxonomy or user fields?
