I came across a fascinating suggestion by Prof. Y. M. Grintz in his book פרקים בתולדות בית שני (Chapters in the History of the Second Temple), p. 36. He pointed out that in the first three generations after Shimon Ha'tzaddik, there was always an instance of one sage being from outside of the Land of Yehudah:
- Antignos from Socho in the Galilee1
- Yosei ben Yoezer from Tzredah in the Shomron
- Nitai Ha'arbeli from Arbel in the Galilee
Grintz noted that there was likely no shortage of great sages in Yehudah, but there was a particular need for a leader from outside of Yehudah: Prior to the mid-Chashmonaim period, Yehudah, the Galilee and Shomron were separate provinces, first during the Persian period and then during the Hellenistic period. It seems, therefore, that to properly govern the Jews of northern Israel there was need in the Sanhedrin for a sage who was intimately familiar with the going-ons of that area.
I will add that in later sources we find many differences between the halacha of Yehudah and the halacha of the Galilee (and, on occasion, also the halacha of Shomron and the halacha of Ever Hayarden), further necessitating deep familiarity with the conditions and reality of those areas.
As for why this was only established in the Hellenistic period and not prior, Grintz noted that Ezra was given legal jurisdiction over the entirety of the Ever Ha'nahar province (Ezra 7:25), so it seems that a centralized legal-halachic administration in Yerushalayim with smaller localized offshoots was enough at the time, even if politically the area was divided into separate sub-provinces (such as Yehud, Shamarin, Pleshet and more). This changed with the Macedonian conquest which took place during the days of Shimon Hatzaddik. No longer having full authority over the various provinces necessitated reshaping the Sanhedrin.
We don't know enough about later Zugot to know whether this model was continued after the time of Yehoshua ben Perachyah and Nitai Ha'arbeli. The northern/southern unity may have been deemd by then no longer necessary because of the conquests of Yochanan Hyrcanus and Alexander Yannai of most of the rest of Eretz Yisrael, once again allowing for a more centralized halachic government. At this point the Zugot model may have continued simply because it had become traditional, but this is only personal speculation.2
In my opinion, the model became necessary once again during the post-Herodian Roman period, circa the time of Rabban Gamliel I, when Judea, Samaria and the Galilee were separate provinces. However, it doesn't seem that there was a separate Av Beit Din during his time, nor during the time of his father, Shimon ben Hillel. It's possible that Rabban Gamliel was familiar enough with the special circumstances of the north to manage to halachically lead the entire country properly. This might be hinted by his ties with the people of the north (Tosefta Shabbat 14:2: Rabbi Chalafta, a Galilean sage, testifies to having met Rabban Gamliel in Yerushalayim). In any case, it seems that the model was essentially resurrected in the time of Rabban Shimon ben Gamliel I, whose Av Beit Din was Rabban Yochanan ben Zakkai, who had previously lived for 18 years in the Galilee (Mishna Shabbat 16:7; Mishna Shabbat 22:3; Yerushalmi Shabbat 16:8; Bavli Brachot 34b). However, by this time the model was no longer known by the term "Zugot". It's possible that there were some key differences between the two stages of the model, further clarifying why the term "Zugot" no longer described the model, but lacking enough information regarding the time of the Zugot, it's difficult to say. The usefulness of Rabban Yochanan ben Zakkai's appointment seems most evident in an epistle sent by the two to the people of the Galilee regarding ma'asrot (Midrash Tannaim Devarim 26:13). Rabban Yochanan ben Zakkai being a more familiar figure to the people of the Galilee might have elicited a more positive response from them.
After the Churban, Rabban Yochanan ben Zakkai did not appoint a northern Av Beit Din as a partner. In a paper I wrote once for a class in university, I argued, based on many sources (too many to bring here) that Rabban Yochanan ben Zakkai believed that in the post-Revolt era there was a necessity for a decentralized halachic authoritative model, as so many different areas of the land needed strong, supportive leaders to help get back up on their feet. So we find that most sages were spread across the land. It was only in the time of Rabban Gamliel II that the model became more centralized once again, and he seems to have appointed the northern sage Rabbi Tzaddok to be his right-hand man (quite literally, see Tosefta Sanhedrin 8:1; many other sources establish that Rabban Gamliel greatly respected Rabbi Tzaddok). However, by this time there were more batei midrash around the land, and Rabban Gamliel II was also known for travelling around the land and the world, checking up on various Jewish communities, as well as meeting non-Jewish leaders, so the model was apparently no longer necessary.
In short, essentially, the Zugot model was deemed necessary when there were difficulties in having a centralized halachic administration governing the whole of Eretz Yisrael. The Zugot model fell out of use largely during times it was no longer needed. There are some specific periods where it seems the model was at least partially resurrected, and then it fell out of use once again.3
1 Not officially a member of a Zug according to known Chazalic sources, but according to the Rambam, a close associate of his was Rabbi Elazar ben Charsom, who was both the Kohen Gadol of the time and had a large estate in Har Ha'melech in Yehudah (Eicha Rabbah 2:4) and was deeply involved in the politics of Yehudah (see partial summary here, and for more information, see Chaim Chefetz's article referenced there).
2 Interestingly, a 14th century version of Toledot Yeshu refers to Shimon ben Shetach as the head of the Beit Midrash Ha'gadol in Teverya, an institution known mainly from late 2nd century CE sources and onwards. While older versions of Toledot Yeshu are thought to date to circa the 3rd century CE, they do not include this piece of information.
Furthermore, Teverya was only erected several decades after Shimon ben Shetach's time, so this supposed biographical note is fictitious.
3 Regarding the First Temple period, there isn't much information, but I would guess that when the kingdom was unified, one court was enough, much as one king managed to rule the entire land. When the kingdoms were divided, it's possible that two separate courts were established, given that Yerov'am took great pains to block the Israelites from going up to the Mikdash in Yerushalayim, necessitating the creation of a northern court system.