We study the decoherence of two ferro- and antiferromagnetically coupled spins that interact with a frustrated spin-bath environment in its ground state. The conditions under which the two-spin system relaxes from the initial spin-up - spin-down state towards its ground state are determined. It is shown that the two-spin system relaxes to its ground state for narrow ranges of the model parameters only. It is demonstrated that the symmetry of the coupling between the two-spin system and the environment has an important effect on the relaxation process. In particular, we show that if this coupling conserves the magnetization, the two-spin system readily relaxes to its ground state whereas a non-conserving coupling prevents the two-spin system from coming close to its ground state.