Gemara

Beraisa: Olei Bavel (the exiles that returned to Eretz Yisrael with 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 - The following 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): The cities listed are not the only walled cities. Moshe conquered "Shishim Ir... Mamleches Og...Betzuros Chomah!" Rather, the Mishnah lists cities known to have had a wall. If there is a tradition about another city that it had a wall when Yehoshua entered Eretz Yisrael, the Mitzvos of walled cities (one who sells a house has a year to redeem it, a Metzora cannot stay there) also apply to it, 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 Beraisa #2 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!

Yevamos 82b - Beraisa - Seder Olam: "That your fathers inherited, and you will inherit" - there is a first and second inheritance, not a third (the second Kedushah never ceased).

R. Yochanan: R. Yosi taught Seder Olam.

Rishonim

Rambam (Hilchos Beis ha'Bechirah 6:16): Even though the Kedushah of Eretz Yisrael regarding Shemitah and Ma'aseros was temporary, the Kedushah of the Azarah and Yerushalayim was permanent, because their Kedushah is the Shechinah, which is not Batel - "V'Hashimosi Es Mikdesheichem". The Mitzvos of Shemitah and Ma'aseros were due to Kivush Rabim (conquest), so once the Nochrim took the land, the conquest (by Yisrael) was Batel, so it was no longer considered Eretz Yisrael. 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.

Kesef Mishneh: I do not know why Chazakah is stronger than conquest to cause the land to keep its Kedushah after it was taken.

Rambam (Hilchos Terumos 1: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, in order 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: We find many Tana'im who 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 (that R. Meir ate Yerek). The Rambam understands that 'permitted Beis She'an entirely' connotes that he totally permitted 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! We can answer the latter question by saying that it is exempt only from things which are only mid'Rabanan in Eretz Yisrael, such as 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. 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.

Beis Yosef (DH u'Mah she'Chosav Aval and DH u'SMaG): The Rambam said that Olei Bavel were Mekadesh part of Eretz Yisrael permanently. This was mid'Oraisa regarding laws other than Terumos and Ma'aseros. Alternatively, it was mid'Oraisa to obligate Terumos and Ma'aseros when the majority of Benei Yisrael will be in Eretz Yisrael. (The Rambam learns from "Ki Savo'u" that this is a condition for Terumah to be mid'Oraisa.)

Rambam (26): Terumah nowadays and even the days of Ezra is only mid'Rabanan. It is mid'Oraisa only when all of Yisrael are in Eretz Yisrael.

Rebuttal (Ra'avad): We hold like R. Yochanan, who says that Terumah is mid'Oraisa nowadays. It seems that the Rambam himself says so above. Only regarding Chalah we require all of Yisrael to be in Eretz Yisrael.

Beis Yosef (YD Reish Siman 331 DH u'Mah she'Chosav): R. Yochanan said so according to R. Yosi, who taught Seder Olam. Perhaps R. Yosi himself holds that Terumah is mid'Rabanan. Alternatively, even the opinion who says that Terumah is mid'Oraisa today means only that the second Kedushah was permanent, and Terumah would be mid'Oraisa if most of Benei Yisrael were in Eretz Yisrael. The Rambam said that Benei ha'Golah were Mekadesh parts of Eretz Yisrael. This was mid'Oraisa for things other than Terumah.

Rambam (Hilchos Shemitah 12:15): When Benei Yisrael entered Eretz Yisrael the second time with Ezra, this gave Kedushah to all the cities surrounded by a wall at the time. The second entrance was like the first in the time of Yehoshua, in which they counted Shemitin and Yovelos, were Mekadesh walled cities and became obligated in Ma'aser.

Pirush ha'Mishnayos (Eduyos 8:6): All agree that the second Kedushah, which Olei Bavel settled, was permanent.

Gra (YD 331:6): According to R. Yosi it was mid'Oraisa; Chachamim say that it was mid'Rabanan. This is better than Rashi's explanation, that all agree that the second Kedushah was mid'Oraisa, and they argue about whether or not it was permanent.

R. Shimshon (Shevi'is 6:1 DH Yerushalmi (Sham)): In the Yerushalmi, R. Yosi b'Rebbi Chanina says that Olei Bavel became obligated in Mitzvos ha'Aretz mid'Oraisa. R. Eliezer says that they voluntary accepted Ma'aser on themselves. R. Ba says that R. Chalifta is lenient about Terumah (nowadays) because he holds that they voluntary accepted it on themselves, i.e. it is mid'Rabanan. However, it is astounding to say that Terumah was mid'Rabanan in Bayis Sheni. Rather, grain, wine and oil were mid'Oraisa, and they accepted on themselves other produce. Also, even regarding grain, wine and oil it is considered that they accepted it on themselves because they were not commanded to be Mekadesh everything inside the borders like Yehoshua was. R. Yosi holds that they were commanded; therefore, the Kedushah applies even nowadays. Presumably, R. Eliezer would say that they accepted on themselves only as long as Bayis Sheni will stand.