Gemara

(Rav Mesharshiya): The Mezuzah is Chovas ha'Dar (a Mitzvah incumbent on the resident).

Bava Metzia 101b - Question: Who must supply the place in which to put the Mezuzah?

Answer (Rav Sheshes - Mishnah): Shimon supplies anything that does not require a craftsman.

One can put the Mezuzah in a hollow reed and hang it from the doorpost. This does not require a craftsman!

(Beraisa): If Reuven rented a house to Shimon, Shimon must affix a Mezuzah. When he leaves, he does not take it with him. If a Nochri owns the house, he takes it with him.

A case occurred in which a man took the Mezuzah with him. His wife and two children died. The case was, a Yisrael owned the house.

Rishonim

Rambam (Hilchos Mezuzah 5:11): If Reuven rents a dwelling from David, Reuven must bring a Mezuzah and affix it, even if he must pay for affixing it, for Mezuzah is obligatory on the resident, and not on the house. When he leaves, he may not take the Mezuzah with him. If he rented it from a Nochri, he takes the Mezuzah when he leaves.

Hagahos Maimoniyos (7): The Ri exempts a house rented from a Nochri from Mezuzah. "Beisecha" excludes another's house (i.e. of a Nochri). This is why a borrowed Talis is exempt from Tzitzis for 30 days; after 30 days it is liable only mid'Rabanan, lest people say that it is his. People will not think that the Nochri's house is of the Yisrael. We say that Mezuzah is Chovas ha'Dar to exempt a Yisrael who rents his house to a Nochri. However, why doesn't "Beisecha" exclude a Yisrael who rents from a Yisrael? If you will say that rental acquires, also borrowing acquires! The Rambam obligates a Yisrael who rents from a Nochri.

Hagahos Ashri (Shabbos 2:7): One may not remove a Mezuzah, even to put it on another house.

Rashi (Pesachim 4a DH Chovas): Mezuzah is Chovas ha'Dar because it protects him.

Maharil (Minhagim, Hilchos Mezuzah 4): The mayor (a Nochri) asked Reuven for a Mezuzah to put on his fortress. He promised to do good to him all his life. Reuven fears that if he refuses, the mayor will make great problems for him. There are many reasons why it is forbidden to give a Mezuzah to a Nochri.

Maharil (Teshuvos Chadashos 123): We buy Seforim, Tefilin and Mezuzos from Nochrim up to their value (Gitin 45a). If not for concern lest theybe incited to steal, we would buy from them for more than the value, lest they disgrace them. All the more so l'Chatchilah one may not give to them. Even if the Nochri says that he will guard it, this is only as long as he is not harmed. If he is harmed, he will revolt and regret it, just like in the future when Hash-m will offer them the Mitzvah of Sukah. (When it is painful, they kick the Sukah and leave - Avodah Zarah 3a.) Chesed that they do is called Chatas, for they do so only to be haughty and revile us and disgrace us more. They will disgrace the Mezuzah and our Mitzvah, and more Chilul Shem Shamayim will result than Kidush Shem Shamayim. Further, after he dies, what will happen when it falls to his heirs?! Also, a Galach (priest of idolatry) will mention it and revile him for it, and surely the Mezuzah will be ruined and disgraced. Also, one may not sell sell a Talis with Tzitzis to a Nochri, lest a Yisrael assume that he is a Yisrael and he will travel with him and the Nochri will kill him. The same concern applies here, lest a Yisrael lodge with him or travel with him. Even though it is on a fortress, one might think that a Yisrael servant of the noble lives there. The concerns for Zonah also apply (perhaps a Yisraelis harlot will think that he is a Yisrael and have Bi'ah with him, or he will give it to a Nochris Zonah,and she will says that a Yisrael gave it to her - Rashi Menachos 43a DH Zonah). One should try to dispel him to avoid enmity, e.g. 'it is very Kodesh for us, but it will not help you, just like the spice Sheves, which helps only for people who observe Shabbos. Since we mention in it Yichud Hash-m and Ol Malchus Shamayim and Ol Mitzvos whenwe enter and leave the house, these merits protect us. For a Nochri, it is the way of Minus (idolatry), and it arouses prosecution that they do the opposite! The fact that one Nochri fortress (with a Mezuzah) was saved was a coincidence. We have a tradition that no harm will come to a Yisrael who guards his faith without wavering to cater to nobles, and he will find grace in their eyes. They will establish us to be truthful and not try further to deter us. The only exceptions are what Chachamim permitted to those who needed to be close to the kingdom to petition for Yisrael.

Poskim

Shulchan Aruch (YD 291:2): If Reuven rents a dwelling from David, Reuven must affix a Mezuzah and prepare a place for a Mezuzah.

Rema: Even if he rented the house b'Chezkas (with the understanding) that it has a Mezuzah (but it does not), this is not a Mekach Ta'os (mistaken sale).

Beis Yosef (DH v'Chosav, citing R. Mano'ach): We say (Pesachim 4b) that a person is happy to do a Mitzvah with his money.

Birkei Yosef: If Levi rented a house b'Chazakah that it has no Mezuzah, but it does, and Levi says that he rented it just in order to do the Mitzvah, this is like I wrote in OC 437:5. (If one rented a house b'Chazakah that it was not checked for Chametz, but it was, this is a Mekach Ta'os only if he cannot create a Chiyuv to check it again, and he truly rented it in order to check it, and not for the sake of living there.

Shulchan Aruch (ibid): When he leaves, he may not take the Mezuzah with him.

Rema: If he is adamant about the money, the new tenant must pay him for the Mezuzah.

Beis Yosef (DH u'Mah she'Chosav v'Lo, citing R. Mano'ach): If the previous owner is particular about the money, it is good to pay him, but we do not remove it.

Shulchan Aruch (ibid): If he rented it from a Nochri, or the new tenant will be a Nochri, he takes the Mezuzah when he leaves.

Beis Yosef (ibid.): R. Mano'ach says that the Gemara said that if a Nochri owns the house, he takes it with him. The same applies if the next tenant will be a Nochri. This is obvious.

Rema: If a Nochri requested a Mezuzah to put it on his door, one may not give to him. It seems that if there is concern for enmity, and he may harm him if he does not give to him, it is permitted.

Gra (2): This is like we find on 26a (a Bas Yisrael may not help a Nochris give birth, for child will serve idolatry. However, it is permitted for pay, lest there be animosity.)

Magen Avraham (19:1): We do not bless on tying Tzitzis on the garment, for the Mitzvah is wearing it. Why do we bless on affixing a Mezuzah? The Mitzvah is only when he lives there! It seems that we bless because normally, one affixes a Mezuzah when he dwells there, but one ties Tzitzis even before wearing the garment. Perhaps one who affixed it earlier would bless 'Asher Kideshanu... to dwell in a house with a Mezuzah' when he enters.

Birkei Yosef (19:2): Yad Aharon says that writing a Mezuzah is like tying Tzitzis, and affixing it is like wearing the garment. I say that since it is Chovas ha'Dar, entering is like wearing the garment, and he should bless when he dwells! Writing a Mezuzah is like spinning threads, affixing it is like tying the Tzitzis to the garment, and dwelling in the house is like wearing the garment. Why do we bless on affixing it? I answer that we delay the Berachah until his final engagement with the Mitzvah, just like we bless when wearing the Talis.

Mishnah Berurah (4): One blesses on a Mezuzah only if he will immediately enter to live, or if he already lives there (Birkei Yosef; the Magen Avraham agrees, if one analyzes his words well).

R. Akiva Eiger (Teshuvah 9 DH v'Agav, cited in Pischei Teshuvah 291:4): If one moves to a new house that already has a Mezuzah, he must bless, for it is a new Mitzvah for him. Also one who went to the market for several hours, or went away on business for days, should bless when he returns, for he was exempt and now he is liable again, like one who left the Sukah and returned, or took off his Talis and put it on again much later. His household is exempt, for it is not their house. It is like a borrowed house. The Birkei Yosef exempts even the first case. This requires investigation.