Gemara

(Rav Huna brei d'Rav Yehoshua): Even the opinion that Terumah is mid'Oraisa nowadays says that Chalah is only mid'Rabanan!

(Beraisa): "Ki Savo'u (plural)" - when all of you come (to Eretz Yisrael), not when a minority comes.

Only a minority of those exiled to Bavel returned with Ezra to Eretz Yisrael.

Chulin 7a (Beraisa): Olei Bavel (the exiles who returned) 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 (Beraisa - 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 - R. Yishmael b'Rebbi Yosi): If a city had a wall when Yehoshua entered Eretz Yisrael, the Mitzvos of walled cities (Bayis Ir Chomah, Shilu'ach Metzora'im) 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 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!

Nazir 36b - Question (Beraisa): If one Se'ah (measure of grain) fell into a box of Terumah and one Se'ah fell into a box of Chulin, and one Se'ah (we do not know which) was Terumah, we say that the Terumah fell into the Terumah, and the Chulin into the Chulin.

If the Torah obligates one for eating an olive's worth (of Isur) within a half loaf of a mixture, why are we lenient to say this?

Answer: The Beraisa discusses nowadays that Terumah is only mid'Rabanan, therefore we are lenient.

Yevamos 82a - Question: R. Yochanan established the Beraisa even when the boxes did not have more than a Se'ah at the beginning (if Terumah fell in the Chulin, it is the majority). Above he said that Terumah is mid'Oraisa nowadays. How can he be so lenient about an Isur mid'Oraisa?

Answer: R. Yochanan said that R. Yosi holds that Terumah is mid'Oraisa nowadays. This Beraisa is like Chachamim.

Contradiction (Beraisa in Seder Olam): "Asher Yarshu Avosecha vi'Rishta" -- the verse alludes to two inheritances (of Eretz Yisrael, in Yehoshua's time and in Ezra's time). There will not be a third (because Ezra's Kedushah never lapsed)!

(R. Yochanan): We assume that a Stam Beraisa in Seder Olam is R. Yosi.

Nidah 46b (Beraisa - R. Yosi): If a minor reached Onas ha'Nedarim (the year before adulthood), if he separates Terumah it takes effect.

Question: If his separation is only mid'Rabanan, how can Terumah mid'Rabanan exempt Tevel mid'Oraisa?

Answer: R. Yosi holds that Terumah is mid'Rabanan nowadays.

Question: R. Yosi taught in Seder Olam that there will not be a third inheritance!

Answer: R. Yosi taught this, but he disagrees.

Rishonim

Rambam (Hilchos Beis ha'Bechirah 6:14,15): Yehoshua's Kedushah of Eretz Yisrael regarding Shemitah and Ma'aseros was temporary. The Mitzvos of Shemitah and Ma'aseros depend on conquering the land, so once the Nochrim took it, Yisrael's conquest 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.

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 (26): Nowadays, even where Olei Bavel took possession, the obligation to tithe is mid'Rabanan. Terumah is mid'Oraisa only in Eretz Yisrael when most of Benei Yisrael are there. We learn from "Ki Savo'u", when all of Yisrael come, like the first inheritance (in the days of Yehoshua) and like it will be in the future in the third inheritance. In the days of Ezra only a minority came, so the Chiyuv was not mid'Oraisa. It seems that also Ma'aser is only mid'Rabanan nowadays.

Rebuttal (Ra'avad): We hold like R. Yochanan, who says that nowadays Terumah is mid'Oraisa. The Rambam himself seemed to say so in Halachah 1. "Ki Savo'u" explains why Chalah is only mid'Rabanan nowadays (Kesuvos 25a).

Kesef Mishneh: The Magid Mishnah (Isurei Bi'ah 20:3): says that the Halachah follows R. Yochanan against Reish Lakish when they themselves argue. Here, they argue like R. Yosi and Chachamim, so this rule does not apply. Rather, the Halachah follows Chachamim. Also, the Sugya in Kesuvos (25a) connotes that Terumah is mid'Rabanan nowadays. Also, even though the Gemara (Yevamos 82b) says that R. Yochanan holds like R. Yosi, perhaps it really means that he explains R. Yosi. Also, the Gemara (Nidah 46b) suggests that R. Yosi himself holds that Terumah is mid'Rabanan nowadays.

Question: In Yevamos (82b), R. Yosi expounds that there is a first and second inheritance, but not a third, for the second Kedushah never ceased. R. Yochanan proves from here that R. Yosi holds that Terumah is mid'Oraisa nowadays. According to the Rambam in any case it is mid'Rabanan, for the majority did not return to Eretz Yisrael!

Answer (Kesef Mishneh): The Rambam explains like R. Chananel (brought in Tosfos Yevamos 82b DH Yerushah), that the first inheritance was of the Avos, and the second was in the days of Yehoshua. At that time all of Yisrael were there, therefore the Kedushah for Terumah was mid'Oraisa, and R. Yosi holds that it was permanent.

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 for laws other than Terumos and Ma'aseros. Alternatively, it is mid'Oraisa for Terumos and Ma'aseros for when the majority of Benei Yisrael will be in Eretz Yisrael. Perhaps the Rambam had a source that exempts even Terumah from "Ki Savo'u." A Gemara (Nazir 37a) says 'the Beraisa discusses nowadays, that Terumah is only mid'Rabanan.' It did not say 'the Tana holds that Terumah is mid'Rabanan nowadays'. This suggests that this is the Halachah.

Defense (of Rambam - Taz YD 331:1): The Gemara says that even the opinion that Terumah is mid'Oraisa nowadays says that Chalah is only mid'Rabanan. The Rambam rules like the opinion that even Terumah is mid'Rabanan, and surely Chalah is also mid'Rabanan!

Rebuttal (Nekudas ha'Kesef): Even the opinion that Terumah is mid'Oraisa nowadays says that Chalah is mid'Rabanan because "Ki Savo'u" applies to Chalah, but not to Terumah. The opinion that Terumah is mid'Rabanan has a different source, i.e. Kedushas ha'Aretz is Batel. No one says (like the Rambam) that Ki Savo'u" applies to Terumah!

Poskim

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

Shach (3): Whenever the Rambam or Shulchan Aruch mentions Terumos and Ma'aseros mid'Oraisa, this is when most of Benei Yisrael are in Eretz Yisrael.

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.

Gra (6): The Rambam and Shulchan Aruch rely on a Yerushalmi that says that in the days of Ezra, Terumah was only mid'Rabanan. In the Bavli, R. Yosi says that the second Kedushah was permanent; Chachamim disagree. Rashi says that all agree that Terumah was mid'Oraisa in the days of Ezra. The Rambam's explanation is better. All agree that the second Kedushah was permanent, just Chachamim say that it is mid'Rabanan.

Rema: Some argue and say that nowadays the obligation in Eretz Yisrael is mid'Oraisa. This is not the practice.

Tur (DH Pa'amim, towards Sof ha'Siman): Even according to the opinion that Terumah is mid'Oraisa nowadays, this is only if one eats what he grew. All agree that the obligation to tithe what is bought or sold after Miru'ach is mid'Rabanan.