The Mishnah in Sukkah 34b says that an esrog of urla (fruit from the first three years after the tree was planted) and that of terumah temeiah are unfit for use in fulfilling the mitzvah. The Gemara (35a) explains that this is because one of the requirements of the mitzvah is that one must be able to eat the esrog. Since one may not eat urla or terumah temeiah they are unfit for the mitzvah.
Rashi there explains that this requirement stems from the pasuk of “lachem,” which teaches us that the esrog must be available to the one using it for all purposes. Tosafos and other Rishonim point out that according to Rashi an esrog that one is not permitted to eat is only unfit for use of the mitzvah on the first day of Yom Tov, when the halacha of lachem is required. However, for the remainder of the Yom Tov, when there is no requirement of lachem and one may even borrow an esrog to fulfill the mitzvah, the esrog does not have to be fit for consumption.
The Rambam (Hilchos Lulav 8:9) explicitly says that an esrog that is forbidden to be eaten is unfit for the mitzvah on all seven days of Yom Tov. He explains his ruling in his pirush to Mishnayos on this Mishnah. The Rambam says that the requirement that the esrog must be fit for consumption is drawn from the pasuk, “pri eitz hadar.” He explains that something that is forbidden to be eaten or that must be burned cannot be called a pri (fruit), for it is not something that may be eaten. Thus the Rambam rules that such an esrog may not be used for the mitzvah on all seven days of Yom Tov.
Ma’aser sheini may only be eaten in Yerushalayim. Tosafos (Sukkah 35a d”h lifi) says that an esrog of ma’aser sheini that is outside of Yerushalayim may be used for the mitzvah since there is a way whereby the esrog may be eaten, namely by bringing it to Yerushalayim. The Rambam (Hilchos Lulav 8:2) says that outside of Yerushalayim, an esrog of ma’aser sheini may not be used for the mitzvah.
Based on the Rambam’s explanation of why an esrog of urla and terumah temeiah are unfit for the mitzvah, we can understand the reason for this ruling. Since the Rambam explained that in order to be fit for the mitzvah the fruit must be edible in order for it to be called a fruit, we can understand that the fruit must be practically edible in the place where it is. The fact that it may be permitted to be eaten if it is brought to another city does not render it a fruit in this city. Since it is forbidden to be eaten where it currently is, it is not referred to as a fruit.
But Tosafos learns like Rashi in that the reason why an esrog that is forbidden to be eaten is unfit for the mitzvah is because of the pasuk of lachem. As has been explained, the pasuk of lachem teaches us that one must own the esrog in a manner in which he can do with it as he pleases – even eat it. If it is forbidden to be eaten he does not completely own it. Therefore Tosafos does not require that the esrog, in a practical sense, must be able to be eaten in the city that it is in; rather, if one has a way to eat it, it is considered as if he owns the esrog regarding consumption. The fact that he has an opportunity to eat it suffices, in order to show that he indeed owns the esrog entirely.
The Rambam writes (Hilchos Lulav 8:1) that an esrog of avodah zarah should not optimally be used for the mitzvah; however, if used, it is a fulfillment of the mitzvah. The Acharonim are bothered by an obvious question. If one may not eat something of avodah zarah, how then may such an esrog be used for the mitzvah?
The sefer, Harirai Kedem, suggests that a careful reading of the Rambam in Hilchos Avodah Zarah will shed light on this question. The Rambam writes (7:2) that avodah zarah is forbidden to be beneficial to anyone; one who derives any benefit will receive lashes. Regarding urla and other things that one cannot derive benefit from, the Rambam (Hilchos Ma’achalos Assuros 8:16) writes that one does not receive lashes for having derived benefit. We see that he only receives lashes if he benefited from avodah zarah. The reason for this is because the actual prohibition regarding avodah zarah is to not derive benefit, whereas regarding all other things whereby benefit is forbidden the issur is actually to not eat it (which also includes not deriving any benefit).