It looks like SimpleX has actually thought about the difficult problems with having multiple servers in a private messenger system.
I haven’t read in enough detail to be sure that they’ve succeeded in solving the problems, but they’re doing better than most of the other things I’ve looked at in this space. Signal could probably learn some lessons.