Gemara

R. Yochanan Any place where Sheluchim (reporting Kidush ha'Chodesh) for Nisan reach, but Sheluchei Tishrei (they may not travel on Rosh Hashanah or Yom Kipur) do not reach (before the 15th of the month) must keep two days of Yom Tov;

They must keep Yom Tov Sheni even regarding Pesach. This is a decree lest they not keep Yom Tov Sheni of Sukos.

Kesuvos 25a - Beraisa: Any of the following is a Chazakah (of Kehunah):

In Eretz Yisrael, giving Birkas Kohanim or receiving Terumah at the granaries;

In Surya or any place where messengers arrive to inform which day was declared Rosh Chodesh, Birkas Kohanim is a Chazakah, but receiving Terumah is not.

Bavel is considered like Surya.

R. Shimon ben Gamliel says, even Alexandria used to be like Surya, since Beis Din was fixed there.

Rishonim

The Rif and Rosh (1:7) bring our Gemara verbatim.

Rambam (Hilchos Kidush ha'Chodesh 3:12): In some places Sheluchei Nisan would reach there, but Sheluchei Tishrei would not. Letter of the law they should be allowed to keep only one day of Yom Tov on Pesach and two days on Sukos. However, Chachamim did not distinguish, and required them to keep two days even regarding Shavu'os.

Rambam (5:9,10): Keeping one day of Yom Tov does not depend on proximity to Yerushalayim. Even if a place is within five days journey, perhaps Sheluchim were never sent there. Perhaps Yisraelim settled there only after Kidush ha'Chodesh was fixed according to calculation. Or perhaps there was hostility between governments like there was between Galil and Yehudah at the time of the Mishnah, or Nochrim would not allow Sheluchim to pass through. Mitzrayim and most of Surya are within 10 days journey, nevertheless they keep two days.

Source (Or Some'ach 5:11): The Yerushalmi and Kesuvos 25a prove that Sheluchim did not arrive in Alexandria and Surya.

Rambam (11): Any place more than 10 days journey from Yerushalayim keeps two days, for Sheluchei Tishrei would not reach there every year (e.g. if Rosh Hashanah and Yom Kipur are on weekdays, there are only nine days on which one may travel before Sukos). If a place is within 10 days journey:

If Yisraelim lived there during Kivush Sheni (starting from Bayis Sheni, as long as) when Kidush ha'Chodesh was through witnesses, it keeps one day of Yom Tov. This applies to places like Lud, Yavneh and Tiverya;

If it is in Surya, such as Tzur, Dameshek or Ashkelon, or Chutz la'Aretz such as Mitzrayim, Amon and Mo'av, people conduct according to the tradition of their ancestors (there).

Chazon Ish (OC 132:1): In Eretz Yisrael, the Rambam does not require a tradition to keep one day. This is because most of Eretz Yisrael was in the hands of Yisrael until Kidush through witnesses ceased. Therefore, we are not concerned lest Sheluchim did not arrive there unless there is such a tradition. Most of Chutz la'Aretz was in the hands of Nochrim, therefore we are stringent unless there is a tradition to keep one day. The Rambam would not be stringent to keep two days if it was a Safek. Just like one may not make Kodesh Chol, he may not make Chol Kodesh.

Rambam (12): If a place within 10 days of Yerushalayim is Surya or Chutz la'Aretz and does not have a custom, or if it is a new city built in the wilderness of Eretz Yisrael or it was inhabited by Yisrael only now, it keeps two days like the majority of the world.

Question: Why do people in Tzur keep Yom Tov Sheni? We know that Yisraelim lived there (Avodah Zarah 11b)!

Answer (Teshuvas Rambam Blau 125 or Freiman 71): If it is not clear to us that Sheluchim arrived in a certain place, they must keep two days. We follow the custom in every place.

Question: Hilchos Yom Tov (1:21) the Rambam says that Benei Eretz Yisrael keep two days only on Rosh Hashanah. Here, the Rambam says that it does not depend on being part of Eretz Yisrael, rather, on whether or not Sheluchim reached there!

Answer (Tzitz Eliezer 3:23:5 DH v'Nir'eh l'Aniyas): The Rambam holds that in the places settled by Olei Bavel, no one keeps two days. Everywhere else depends on whether or not Sheluchim reached there.

Question (Ritva 18a DH v'Yesh): Eretz Yisrael is 400 Parsah (about 1200 kilometers) by 400 Parsah. Even if Yerushalayim was in the middle, the ends are 20 days journey away, so Sheluchim could not reach there! The Gemara (Ta'anis 10a) says that people from the ends of Eretz Yisrael returned from Yerushalayim in 15 days. If so, they needed to keep two days of Yom Tov. Why does everyone in Eretz Yisrael keep only one day (except for Rosh Hashanah), but those in Chutz la'Aretz keep two days?

Answer (Ritva): When they were Mekadesh according to witnesses, even Chachamim knew which day was Rosh Chodesh only if they heard from Sheluchim. Nowadays, the calendar was fixed and we know the true day. However, it was enacted that people continue their old practice regarding Yom Tov Sheni. We follow the majority. Sheluchim did not reach most places in Chutz la'Aretz, so they kept two days. Sheluchim did reach most places in Eretz Yisrael, so they kept only one day.

Avnei Nezer (OC 392:9): The custom is like the Ritva, that all of Eretz Yisrael keeps one day and all of Chutz la'Aretz keeps two.

Question: People more than seven days journey from Yerushalayim would (sometimes) not find out before Yom Kipur. We should decree that such people keep two days of Pesach, lest they keep only one day of Yom Kipur!

Answer (Pnei Yehoshua 21a DH b'Rashi): Since it is dangerous to fast two full days, in such places people rely on the majority (Elul was usually short). Even if it was best to keep two days (if possible), this is a mere stringency, and we would not decree about Pesach lest one not be stringent about Yom Kipur.

Poskim

Shulchan Aruch (OC 496:1): In Chutz la'Aretz we keep two days of Yom Tov due to Safek.

Kaf ha'Chayim (4): If the city is near or within sight of a place that keeps one day, it keeps only one day, similar to Kri'as ha'Megilah.

Eretz Tzvi (41, b'Shulei ha'Michtav): The Ya'avetz (Teshuvah 168) learns from the Rambam that a place in Eretz Yisrael where there never was a city keeps two days. This is an awesome Chidush. According to the Ritva, it keeps one day. Even though the Ritva is Basra, we do not follow him because he did not mention the Rambam and refute him. This shows that he did not see the Rambam's opinion. Had he seen it, perhaps he would have agreed (Rema CM 25:2). Also, 200 Rabanan agreed to the Beis Yosef's rule that the Halachah follows the majority of the Rif, Rambam and Rosh. Since the Rif and Rosh did not discuss this, the Halachah follows the Rambam. Also, perhaps the Halachah follows the Ya'avetz, for he is Basra.

Note: The Shulchan Aruch seems to follow the Ritva.

Tzitz Eliezer (3:23:10): It would seem that Eilat should keep two days of Yom Tov, since it was not part of Eretz Yisrael. It is considered part of Eretz Edom ("Benei Esav ha'Yoshvim... me'Eilat..." - Devarim 2:8). Also, it seems that Sheluchim did not reach there, and it is not even clear whether or not Yisraelim lived there during Kivush Sheni. However, it is clear from Nevi'im that Yisrael conquered and settled it (Melachim 1:9:26 and 2:14:22). The Tana'im were involved with the south, i.e. the entire south, so it seems that Sheluchim did reach there. It appears that even the Rambam would agree that Eilat needs to keep only one day.

Yom Tov Sheni k'Hilchaso (18:4 (10), citing Rav S.Z. Auerbach and Rav Y.S. Elyashiv): Seemingly, Eilat should keep two days. It is surely exempt from Terumos and Ma'aseros, and it is more than 10 days from Yerushalayim. It is not clear if 'our' Eilat is the same city mentioned in Tanach. Perhaps our Eilat was within what Benei Yisrael conquered then. One should be stringent to consider the second day Safek Yom Tov. Rav B.Z. Aba Sha'ul says that one should keep two days, even when this is a leniency.