With the success of dynamical mean-field theories, solvers for quantum-impurity problems have become an important tool for the numerical study of strongly correlated systems. Continuous-time quantum Monte Carlo sampling of the expansion in powers of the hybridization between the “impurity” and the bath provides a powerful solver when interactions are strong. Here we show that the usual updates that add or remove a pair of creation-annihilation operators are rigorously not ergodic for several classes of broken symmetries that involve spatial components. We show that updates with larger numbers of simultaneous updates of pairs of creation-annihilation operators remedy this problem. As an example, we apply the four-operator updates that are necessary for ergodicity to the case of d-wave superconductivity in plaquette dynamical mean-field theory for the one-band Hubbard model. While the results are qualitatively similar to those previously published, they are quantitatively better than previous ones, being closer to those obtained by other approaches.