Gemara

(Beraisa): Ma'aser and Shemitah apply to produce of Surya, like Eretz Yisrael.

The Tana holds that Kivush Yachid (land conquered by an individual, not by all of Klal Yisrael) is valid (the land gets Kedushas Eretz Yisrael).

Chulin 7a (Beraisa): Olei (the exiles that returned to Eretz Yisrael from) Bavel (in the days of Ezra) refrained from conquering many cities that were conquered by Olei Mitzrayim (in the days of Yehoshua);

The first Kidush was temporary (it ended with the first Churban). Olei Bavel left many cities without Kedushah, to help support the poor in Shemitah.

Megilah 10a: Tana'im argue about whether or not the Kedushah ended:

(Beraisa #1 - R. Yishmael b'Rebbi Yosi): These cities (in the Mishnah Erchin 32a) were listed because the returning exiles were Mekadesh them. The first Kedushah lapsed from the time of the Churban.

This shows that he holds that the Kedushah was not permanent.

Contradiction (Beraisa #2 - R. Yishmael b'Rebbi Yosi): There were more walled cities. Moshe conquered "Shishim Ir... Mamleches Og... Betzuros Chomah!" The Mishnah lists known walled cities. The Mitzvos of walled cities (one may redeem a house within a year of selling it, and a Metzora must leave it) apply to any city for which there is a tradition that it had a wall when Yehoshua entered Eretz Yisrael, because the first Kedushah was permanent.

Answer #1: Tana'im argue about the opinion of R. Yishmael b'Rebbi Yosi.

Answer #2: The Tana of the Tosefta is really R. Eliezer bar Yosi:

(Beraisa - R. Eliezer bar Yosi): "Asher Lo Chomah" - ("Lo" is written with an Aleph, to include) even if it does not have a wall now, if it once had one!

Rishonim

Rambam (Hilchos Beis ha'Bechirah 6:16): Ezra did not Mekadesh Eretz Yisrael through conquest, rather, through Chazakah. Therefore, any place where Olei Bavel settled and Ezra was Mekadesh is still Kodesh nowadays, even though the land was taken.

Question (Kesef Mishneh): Why is Chazakah is stronger than conquest?

Rambam (Hilchos Terumos 1:1): Mid'Oraisa, Terumos and Ma'aseros apply only in Eretz Yisrael, whether or not the Mikdash stands.

Source (Kesef Mishneh): This is from the Sifri (Korach) and Bikurim 2:3.

Rambam (4): One who buys land in Surya must separate Terumos and Ma'aseros like one who buys in Eretz Yisrael. This is all mid'Rabanan.

Question: Why did the Gemara need to say that the Beraisa is like the opinion that Kivush Yachid is valid? Even if Surya is not like Eretz Yisrael, Terumos and Ma'aseros apply mid'Rabanan!

Answers (Kesef Mishneh): We answer how to explain the Beraisa even if one will say that it is obligated mid'Oraisa. The Ri Korkus says that the Beraisa connotes that it is mid'Oraisa, for it says 'like Eretz Yisrael.'

Rambam (5): The Kedushah of places settled by Olei Mitzrayim was Batel after they were exiled. Since the first Kedushah was through conquest, it was only temporary. Olei Bavel settled some places. They gave it a permanent Kedushah. Olei Bavel intentionally did not settle some places settled by Olei Mitzrayim, and they did not exempt those places from Terumos and Ma'aseros, (Ri Korkus' text - they exempted them only) so that the poor will rely on them in Shemitah. Rebbi permitted Beis She'an and other places that Olei Bavel did not settle.

Ra'avad: Rebbi exempted them only from Ma'aser of Yerek (vegetables) and fruits that are mid'Rabanan even in Eretz Yisrael.

Kesef Mishneh: Many Tana'im say that the first Kedushah was not permanent. Also, we may rely on Rebbi, who was Basra, and did an act to permit them. Rashi and Tosfos explain like the Ra'avad, that Rebbi permitted only what is similar to what he heard (R. Meir ate Yerek). The Rambam understands that 'permitted Beis She'an entirely' connotes that he totally permitted it.

Ri Korkus: We find in many places that Terumah applies in Chutz la'Aretz. This led Rashi to say that Rebbi exempted only Yerek. Others say that Rebbi exempted only Demai, or only what is bought from a Nochri. Others say that Rebbi exempted only from stringencies of Eretz Yisrael, and permitted leniencies of Chutz la'Aretz. E.g. one may Mevatel it in a majority of Chulin, or eat before tithing. The Rambam totally exempts it.

Ri Korkus: Rashi (Chulin 7a DH Harbeh) explains that they did not Mekadesh many places in order that it would be permitted to plow and plant in Shemitah. A Mishnah (Shevi'is 6:1) explicitly says that wherever Olei Bavel settled one may not work or eat in Shemitah (i.e. Kedushas Shemitah applies fully); wherever Olei Mitzrayim settled one may eat, but he may not work. Also, Rashi says that the poor would get Leket, Shichchah and Pe'ah. If it is exempt from Shemitah because it is like Chutz la'Aretz, it is also exempt from Leket, Shichchah and Pe'ah! To answer the latter question, we can say that it is exempt only from what is only mid'Rabanan in Eretz Yisrael, e.g. Ma'aser of Yerek. Perhaps Rashi holds that the Mishnah is like the opinion that the first Kedushah was permanent. We hold that it was not permanent, so whatever Olei Bavel did not settle may be worked and eaten. This is a poor answer. Perhaps the initial enactment was that Leket, Shichchah and Pe'ah would apply there, but not any laws of Shemitah. Afterwards, they forbade working there in Shemitah because it is part of Eretz Yisrael that received Kedushah previously. The Rambam holds that these places are totally exempt from Terumah (and all Matanos). Some say that he holds that the poor would rely on Sefichim (things that grow by themselves). Sefichim are Hefker where they did not Mekadesh, and forbidden where they were Mekadesh. Or, the poor could hire themselves to work for Nochrim. The words of the Rambam, in order that the poor will rely on them in Shemitah, connote otherwise. Rather, since these places are exempt from all Matanos in other years, in Shemitah they will be willing to support the poor.

Poskim

Shulchan Aruch (YD 331:1): Mid'Oraisa, Terumos and Ma'aseros apply only in Eretz Yisrael, whether or not the Mikdash stands. One who buys a field in Surya must separate Terumos and Ma'aseros mid'Rabanan.

Shulchan Aruch (2): Nowadays, even where Olei Bavel took possession, the obligation to tithe is mid'Rabanan. This was true even in the days of Ezra, because it says "Ki Savo'u", which connotes that all (the majority) of Yisrael come to Eretz Yisrael. In the days of Ezra, only a minority came.