Gemara

53b - Question: Why were the Asheiros forbidden? The Avos owned Eretz Yisrael. One (a Nochri) cannot forbid what he does not own!

Answer: When Yisrael served the Egel, they showed that they approve of idolatry, and consented to Nochri worship of Asheiros in Eretz Yisrael.

71a (Rav Ashi): Nochrim do not acquire through Meshichah. I learn from Rav. He told sellers 'take the money before measuring out wine to Nochrim.'

If a Nochrim acquired through Meshichah, he would acquire once the wine enters the airspace of his Keli, but it is not Yayin Nesech until it reaches the bottom (and mixes with residues of Yayin Nesech)!

Bava Metzia 71b - Version #1 - (Rav Ashi): A Nochri cannot be (or make) a Shali'ach only for Terumah, but for other matters, he can!

Rejection: That is wrong! A Nochri cannot be a Shali'ach for Terumah, for we learn from "Gam Atem" - just like you are Bnei Bris (bound by the covenant of circumcision, i.e. Yisrael or a slave), also your Sheluchim must be. We learn from Terumah that Sheluchim work in general!

Version #2 (Rav Ashi): (A Nochri cannot be a Yisrael's Shali'ach due to "Gam Atem" - your Sheluchim must be Bnei Bris, just like you. This is our source for Shlichus. We learn that only Atem (Yisrael) can have Sheluchim!

Rishonim

Rambam (Hilchos Shluchim 2:1): A Nochri cannot be a Shali'ach for anything. A Yisrael cannot be a Nochri's Shali'ach for anything. It says "you will take Terumah Gam Atem" - just like you are Bnei Bris, also your Sheluchim must be. The same applies to the entire Torah. Also, the Meshale'ach must be a Yisrael in the entire Torah.

Mas'as Binyamin (97): Bava Metzia 71b requires the Meshale'ach to resemble the Shali'ach. Therefore, a Nochri can be a Shali'ach for a Nochri.

Mishneh l'Melech: Mas'as Binyamin 97 was unsure whether a Nochri can be a Shali'ach for a Nochri. The Yerushalmi (Terumos 1:1) proves this he cannot. Also see Reish Perek 6 of Demai.

Machaneh Efrayim (Shlichus 14 DH Im): It seems that the Bavli argues. It holds that Nochrim were able to forbade Asheiros in Eretz Yisrael because they were like Shluchim of Bnei Yisrael to serve them!

Note: He must hold that an idolater is like a Nochri. Some say that mid'Rabanan, we are stringent to say that a Nochri is a Yisrael's Shali'ach, but this would not explain why the Torah forbade the Asheiros.

Poskim

Shulchan Aruch (CM 188:1): A Nochri cannot be a Shali'ach for anything. A Yisrael cannot be a Nochri's Shali'ach for anything.

Beis Yosef (DH Ein): It is known that the Halachah follows the latter version. The Rambam rules like this.

Shach (5): A Nochri can be a Shali'ach for a Nochri. This pertains to the sale of Chametz.

Birkas ha'Zevach (in Nachalas Shiv'ah Teshuvah 30 DH v'Agav, cited by R. Akiva Eiger): The Shulchan Aruch says that to exempt from Bechorah, the Nochri pays a Perutah to acquire the place where the animal is standing, and the place acquires for him a share in the animal. Similarly, to buy Chametz, the Nochri acquires the room in which the Chametz is through money or a document, and the room acquires the Chametz for him. This is difficult, for Chatzer acquires due to Shlichus, and a Nochri has no Shlichus! It cannot be through Yad, for then the Nochri would need to be near what he acquires (Bava Metzia 12a)! It is difficult to say that a Nochri can have a Nochri Shali'ach, like Mas'as Binyamin says, and so a Nochri has Shlichus of a Chatzer. Maharam Mintz (5) was unsure about this. R. Yerucham (20:2) says that the Nochri should pay for the ear, or acquire it Agav (along with) land, not through Chatzer. The same should be done for Chametz.

Ketzos ha'Choshen (194:3): We learn from Avodah Zarah 71b that a Nochri acquires through a Chatzer. One's Kelim acquire for him like a Chatzer. Do not say that this is only when the Nochri is there, and it is works due to Yad. One could reject this, for this Gemara is like Rav Ashi, who held (Bava Metzia 71b) that a Nochri can make a Shali'ach! However, the Rema (YD 132:2) rules like this. The Torah included a Chatzer like a Shali'ach, without concern for being Ben Bris.

Magen Avraham (448:4): Mas'as Binyamin allows a Nochri to make a Nochri a Shali'ach to acquire a Yisrael's Chametz. One should not be lenient, for the Yerushalmi and Kidushin 41b connote that it does not work.

Machatzis ha'Shekel (DH v'Tzarich): Even though a Chatzer acquires due to Shlichus, since it is not Ben Bris, it can be a Shali'ach for a Nochri, if we say that a Nochri can be a Nochri's Shali'ach, since neither is Ben Bris. However, the Magen Avraham proved unlike this from the Yerushalmi. It is best to sell to an unmarried Nochris, for a girl's Chatzer works like her Yad. Even though we learn this from Get, there is no exclusion for a Nochris.

Beis Yosef (YD 169 DH v'Im, citing Sefer ha'Terumos): One cannot be Zocheh for a Nochri. Even a Nochri cannot be Zocheh for a Nochri.

Tiferes l'Moshe (YD 168 29:4, cited by R. Akiva Eiger): This disproves Mas'as Binyamin, for here we discuss Zechiyah on behalf of another Nochri! One could answer this with difficulty.

Shulchan Aruch (OC 246:3): If one lent or rented his animal to a Nochri and the Nochri kept it on Shabbos, to avoid the Isur of his animal working on Shabbos) he should make it Hefker, or say that it is acquired to the Nochri.

Magen Avraham (10): The Mordechai requires saying to the Nochri 'my animal is acquired to you'! Even to give it to a Yisrael, it helps only if another was Zocheh for the recipient! Therefore, one must tell the Nochri, so he will intend to acquire.

Machatzis ha'Shekel: One must tell the Nochri himself, for the Magen Avraham (448:4) holds that even a Nochri cannot acquire for a Nochri.

Rema (EH 5:14): All agree that one may give an animal to a Nochri if he will not castrate it himself, rather, he will give it to another Nochri.

Terumas ha'Deshen (299): If a Nochri made another Nochri a Shali'ach to castrate (according to the opinion that forbids them), perhaps Ein Shali'ach l'Devar Aveirah applies also between two Nochrim. Perhaps all the more so it applies, for in general Ein Shlichus l'Nochri!

Beis Shmuel (19): Even if the Nochri made the other Nochri a Shali'ach, it does not take effect (Terumas ha'Deshen 299 and Maharshach 114). This is unlike Mas'as Binyamin 97, who says that it takes effect.

Rebuttal (Hagahos Baruch Frankel, in Rosh Pinah Shulchan Aruch): The Terumas ha'Deshen permits because Ein Shali'ach l'Devar Aveirah, not because Ein Shali'ach l'Nochri!

Pischei Teshuvah (13): Also Keneses ha'Gedolah (Hagahos ha'Tur 188:5) holds that a Nochri can be a Shali'ach for a Nochri.

Mabit (1:145): A Nochri cannot be Zocheh for a Yisrael, i.e. until the recipient made a Kinyan, the giver can retract. Once the recipient got it, he acquired. The Nochri merely transported it, like a monkey. Similar, if a Yisrael sent a Nochri to buy or sell for him, once he sold or bought to or from a Yisrael or Nochri, the Meshale'ach or buyer acquires. Tzeror ha'Kesef says in the name of the Rashba that a Nochri (Tony) can appoint David to claim from Moshe what he owes to Tony, even without Moshe's consent. All the more so, when Reuven and Shimon agree that Tony should acquire from Shimon what he has of Levi, Shimon pardoned his rights and cannot retract from when Tony takes it, for it is already in Levi's Reshus for theft or loss. Every monetary stipulation takes effect. Also, even though a Nochri cannot acquire for a Yisrael, his Kelim acquire for a Yisrael. "Atem" excludes only the Nochri himself. There is no exclusion for his Kelim or Chatzer. Since he agreed to acquire for Levi, it is as if he lent his Kelim or Chatzer to Levi.