Gemara

Rav Yehudah: One may not sound a Shofar of idolatry to fulfill the Mitzvah. If one used it, he was Yotzei.

One may not sound a Shofar of an Ir ha'Nidachas (a city that must be destroyed because most of the people served idolatry) for the Mitzvah. If he did, he was not Yotzei.

This is because Kesusei Michtas Shi'urei (it is as if was already burned and it is less than the Shi'ur).

Sukah 29b - Mishnah: A Lulav of an Asherah (a tree planted for idolatry) or from an Ir ha'Nidachas is Pasul.

Question: Rava taught that one may not take a Lulav of idolatry, but if he did he was Yotzei!

Answer: The Mishnah discusses an Asherah of Moshe; (since Bitul does not apply, it must be burned, and Kesusei Michtas Shi'urei.

Support: Presumably, it is like a Lulav from an Ir ha'Nidachas (which cannot be Batel), with which it was taught.

Chulin 89a (R. Ze'ira): One may use dirt (i.e. ashes) of an Ir ha'Nidachas for Kisuy ha'Dam (covering the blood of a slaughtered bird or Chayah).

Question: Why is this permitted? One may not benefit from the city!

Answer (Rava): Mitzvos Lav Leihanos Nitnu (using something for a Mitzvah is not considered Hana'ah).

Question (Rav Rechumi - Beraisa): One may not sound a Shofar of idolatry to fulfill the Mitzvah.

Suggestion: If one used it, he was not Yotzei.

Answer #1 (Ravina): No, if he used it, he was Yotzei.

Objection (Beraisa): One is not Yotzei with a Shofar or Lulav of idolatry.

Answer #2 (Rav Ashi, to both questions): There is a Shi'ur for a Shofar and Lulav. Since idolatry must be burned, Kesusei Michtas Shi'urei;

This does not apply to Kisuy ha'Dam. Ashes are fine for covering!

Rishonim

Rif: One may not sound a Shofar of idolatry to fulfill the Mitzvah. If one used it, he was Yotzei, because Mitzvos Lav Leihanos Nitnu.

Rosh (3:9) and Ran (DH Amar): This refers to idolatry of a Nochri. Since it can become Batel, it is not Michtas Shi'urei. In Chulin and Sukah the Gemara discusses a Shofar and Lulav of idolatry of a Yisrael, and says that he was not Yotzei because Kesusei Michtas Shi'urei. Similarly, one is not Yotzei with a Shofar offered to idolatry (even) of a Nochri. It cannot be Batel because a verse equates it to a Mes.

The Rif and Rosh (3:1) in Sukah bring the Mishnah there.

Question: How is one Yotzei with a Lulav of idolatry of a Nochri? One must acquire it to be Yotzei. It becomes idolatry of a Yisrael!

Answer #1 (Ra'avad, brought in Ran DH Shel Asherah): The Lulav is Meshamshim (something that serves) idolatry of a Nochri. If the Nochri will Mevatel his idolatry, its Meshamshim are permitted (Avodah Zarah 52b). Therefore, the Lulav is not destined to be burned.

Objection (Ran, ibid.): Perhaps Bitul permits Meshamshim that the Nochri owns, but not Meshamshim that a Yisrael acquired!

Answer #2 (Rosh and Ran, ibid.): On Yom Tov Sheni one can be Yotzei with a Lulav (from an Asherah) borrowed from a Nochri. The Yisrael does not acquire it, therefore Bitul is possible. The Gemara establishes the Mishnah to discuss an Asherah of Moshe, for it is always Pasul.

Ran (ibid.): Rava teaches that b'Di'eved one is Yotzei with idolatry of a Nochri even before Bitul. If it was after Bitul, it would be permitted l'Chatchilah! Since it permitted to people, it is not despised to Hash-m.

Beis Yosef (OC 649 DH v'Chosav ha'Rav): Rashi (DH Lo Yitol) holds that it is despised.

Note: Rashi does not discuss after Bitul, for Rashi (DH v'Im) says that it is Asur b'Hana'ah. However, Rashi (DH Lulav) says that the Lulav was used to sweep in front of idolatry (or is passed in front of the idolatry or thrown at it). This shows that it can be despised even when it is permitted to people.

Rambam (Hilchos Shofar 1:3) One may not sound a Shofar of idolatry to fulfill the Mitzvah. If one used it, he was Yotzei. One may not sound a Shofar of an Ir ha'Nidachas for the Mitzvah. If he did, he was not Yotzei.

Rambam (Hilchos Lulav 8:1): If one of the four Minim was from an Ir ha'Nidachas or from an Asherah that was worshipped, it is Pasul. This is even if the Asherah is Batel from being worshipped. If it was of idolatry, one may not take it, but if he did he was Yotzei.

Kesef Mishneh: The Rambam holds that one is not Yotzei with a Lulav or Shofar of idolatry before Bitul because Kesusei Michtas Shi'urei. After Bitul it is forbidden l'Chatchilah because it is despised, but b'Di'eved one is Yotzei. Some texts (in Rosh Hashanah 28a) say that Rav Yehudah says that one is Yotzei b'Di'eved with a Shofar of idolatry because Mitzvos Lav Leihanos Nitnu. This connotes that he discusses before Bitul. The Rambam rules that b'Di'eved one is Yotzei with a Shofar of idolatry, but not for this reason. He mentions Mitzvos Lav Leihanos Nitnu regarding a Shofar of an Olah, but not regarding a Shofar of idolatry. Alternatively, the Rambam had our text, which does not give Rav Yehudah's reason; Rav Yehudah holds like Rava.

R. Mano'ach: The Rambam says that one is Yotzei with a Lulav of idolatry, i.e. that was used to sweep in front of idolatry. L'Chatchilah it is forbidden for it is despised. One can be Yotzei even on the first day, if he picks it up with intent just for the Mitzvah, but not to acquire it.

Note: It is a big Chidush to say that one may be Yotzei on the first day without acquiring it. Perhaps R. Mano'ach holds that mid'Oraisa there is Bitul even after the Yisrael picked it up; mid'Rabanan there is not. Chachamim were stringent only when the Yisrael intends to keep it. If he intends to be Yotzei (even though this requires a full acquisition) and put it back, it is not called idolatry of a Yisrael and it can be Batel.

R. Mano'ach: Alternatively, he must Mevatel it before taking it. If not, he is not Yotzei mid'Oraisa, for we require "Lachem". On the second day it is Pasul mid'Rabanan, to distance people from idolatry.

Poskim

Shulchan Aruch (OC 586:3): If one sounded a Shofar of idolatry of a Yisrael he was not Yotzei because it can never be Batel, so Kesusei Michtas Shi'urei. If it was of idolatry or Meshamshim of idolatry of a Nochri one should not sound it, but if he did he was Yotzei as long as he did not intend to acquire it. If he intended to acquire it, it is idolatry of a Yisrael.

Beis Yosef (DH Shofar): R. Tam says that even with idolatry of a Nochri one is Yotzei only after Bitul.

Rema. Some say that one is not Yotzei with a Shofar of idolatry even of a Nochri unless the Nochri was Mevatel before Yom Tov.

Magen Avraham (6): If the Nochri was Mevatel on Yom Tov, this is Dichuy after it was Kosher and it is not in his power to fix it, therefore it is Pasul.

Mishnah Berurah (13,14): L'Chatchilah, it is forbidden even after Bitul according to many Poskim, for it is despised. B'Di'eved one was Yotzei even if it was before Bitul, for it is not destined to be burned and Mitzvos Lav Leihanos Nitnu.

Shulchan Aruch (649:3): If one of the four Minim was from an Ir ha'Nidachas or from an Asherah of a Yisrael it is Pasul .If it was from an Asherah of a Nochri one may not take it, but if he did on Yom Tov Sheni he was Yotzei, for we do not require "Lachem".

Magen Avraham (13): Even though it is now Asur b'Hana'ah and Achilah, it could get a Heter through Bitul. We similarly permit an Esrog of Demai because it is permitted if one makes his property Hefker.

Rebuttal (Nesiv Chayim): If he refers to Bitul of the idolatry, this is difficult, for this is not in his power - the Nochri must do it! If he refers to Bitul in a majority of Heter, this is wrong, for it is a Chatichah ha'Re'uyah Lehiskaved (a nice portion fitting to honor someone) which is never Batel! Rather, it is permitted because Mitzvos Lav Leihanos Nitnu, like Rashi says (31b DH v'Im).

Note: Mitzvos Lav Leihanos Nitnu explains why one who takes it does not transgress. However, we require that an Esrog that may be eaten (35a). This is why an Esrog of Orlah is Pasul. Perhaps the Nesiv Chayim means to ask why the Magen Avraham seeks a Heter Hana'ah. I do not know his source to say that an Esrog is Re'uyah Lehiskaved. It is not listed among the seven things that are never Batel (Yevamos 81b).