> Should it not be the case that one of the responsibilities of the quorum is to vote new members in or out? I mean, as a first-class feature of the system.
Indeed. What you're describing is one of the main motivations for Raft. Paxos showed that distributed consensus was mathematically sound, but did little to guide implementors in actually building such a system. Raft is not a fundamentally new consensus algorithm; just an incremental improvement that formalizes many of the improvements that you needed to make to Paxos anyway, like membership changes, log compaction, and multi-decree support from the get go.
If you're interested, the Raft paper is quite readable and goes into this in detail. [0]
> The main problem I see is that in most consensus systems, any member can be nominated as leader. But if the member was inducted during a partition event - which one could do if the partition were long duration - then nominations for new leaders will go out. What happens if the new member gets elected? How do the partitioned machines find that leader when they return? How do the partitioned machines find that leader when they return?
This isn't actually the tricky bit, as it turns out. Communication flows from the leader to the other nodes, so the leader, even if it's a newly-inducted node, will initiate the connections to the partitioned nodes when the partition resolves. (The leader necessarily knows the addresses of the partitioned nodes, because the leader knows about all committed entries, and the identities of all the nodes in the cluster are committed into the Raft log.)
Again, the Raft paper does a great job explaining cluster mebership changes—much better than I can!
[0]: https://raft.github.io/raft.pdf