Gemara

"The Beis ha'Mikdash was built from Shalem (whole) rocks like they were quarried..."

Shlomo (to Chachamim): How can I cut the rocks without iron?

Chachamim: Use the Shamir (a special worm) that Moshe used to engrave the stones of the Efod.

Sotah 48a (Mishnah): After the early Nevi'im died, the Urim v'Tumim ceased. After the Mikdash was destroyed, the Shamir ceased.

48b (Beraisa - R. Yehudah): Shlomo used the Shamir to build the Mikdash.

R. Nechemyah: You cannot say so! It says "these rocks... cut by a saw"!

According to R. Nechemyah, the Shamir was used for the stones (of the Efod). The writing on them cannot be in ink, for it says "engraved"! One cannot cut them with a chisel, for it says "in their fullness"! Rather, one writes on them in ink, and puts the Shamir on them. The Shamir makes the stone cave in under the writing, like a date tree cleaves in summer, even though nothing is missing.

Avodah Zarah 52b (Mishnah): The Chashmona'im buried the rocks of the Mizbe'ach (that the Yevanim had used for idolatry).

Question: Why was Genizah required? They could have forced Nochrim to break the rocks (and Mevatel (nullify) the Isur due to idolatry)!

Answer: We must build the Mizbe'ach with "Avanim Shelemos" (complete rocks).

Question: They could smooth them out later (with a blade)!

Answer: That disqualifies rocks for the Mizbe'ach - "Lo Sanif Aleihem Barzel."

Chulin 18a (Rav Huna bar Rav Ketina): If the Mizbe'ach was dented b'Chagiras Tziporen (enough for a fingernail to get caught while scraping it along the surface), it is Pasul.

Kidushin 31a (R. Eliezer): Once, Chachamim wanted to pay 600,000 gold Dinarim to buy a stone from a certain Nochri for the Efod. He was unwilling to wake his father, so he lost the deal. The next year, a red heifer was born in his herd. He sold it for 600,000 gold Dinarim.

Rishonim

Rambam (14): If a rock was dented b'Chagiras Tziporen, it is Pasul for the Mizbe'ach. We require "Shalem rocks", and also for the Heichal and Azaros.

Question (Tosfos Chulin 18a DH v'Kamah): How were they able to build the Mizbe'ach so smooth, without a dent k'Chagiras Tziporen? The Shamir does not cut smoothly enough for the Mizbe'ach! We concluded that the Chashmona'im could not force Nochrim to break the rocks, and then use them to rebuild the Mizbe'ach, because we cannot use iron to smooth them out. If the Shamir cut smoothly enough for the Mizbe'ach, they had a solution! Zevachim 54a connotes that they used smooth rocks from the river. However, the Beis ha'Mikdash was made from Shalem rocks, and R. Yehudah says that it was through the Shamir!

Tosfos (Zevachim 54b DH Avanim): We cannot say that the Chashmona'im did not use the Shamir because it ceased. A Mishnah teaches that after the early Nevi'im died, i.e. after the first Churban, the Urim v'Tumim ceased. After the Mikdash was destroyed, the Shamir ceased. This refers to the second Churban. If it meant the first Churban, the Mishnah would have taught both of these together. Also, no Parah Adumah was slaughtered during Bayis Rishon (Parah 3:5), so we must say that the episode in Kidushin was during Bayis Sheni. The only way to engrave Avnei Efod is through the Shamir!

Rebuttal #1 (Lo Noda l'Mi DH Bikshu and Me'iri Kidushin 31a DH Kivud (2)): Even though there was no Urim v'Tumim in Bayis Sheni, they made the Bigdei Kehunah as properly as possible. The Shamir had ceased. Perhaps they did not engrave the stones, but merely wrote on them in ink!

Rebuttal #2 (Aruch l'Ner ibid., DH d'Kamrinan): Perhaps the episode was during Bayis Rishon. Chachamim bought a Parah Adumah, but it became Pasul!

Rebuttal #3 (Minchas Chinuch 85 DH Nuchal): Perhaps the episode was during Bayis Rishon. They bought shoulder stones for the Efod, which do not require the Shamir, like the Ramban says (see below).

Answer #1 (Ri Korkus, on Rambam): Chagiras Tziporen does not disqualify rocks for the Heichal and Azaros. The Gemaros in Gitin and Sotah say that they were built using the Shamir. Even though we do not follow that opinion, rather, R. Nechemyah, they do not argue about whether or not the Shamir could be used.

Answer #2 (Aruch l'Ner Sukah 49a b'Tosfos DH v'Im and DH v'Omar): Whenever we quarry rocks, they are not Shalem, for initially they were connected to each other. Therefore, the Torah's insistence of "Shleimos" is after they were built into the Mizbe'ach. Therefore, if it was cut, even if it is smooth, it is not Shalem. If so, we can say that R. Yehudah holds that the Shamir makes them smooth enough for the Mizbe'ach. The Gemara in Avodah Zarah found no solution to make the rocks smooth; this is like R. Nechemyah. R. Yehudah will explain (like the Gemara there sought to prove,) that (we could make them smooth, but) anything used for idolatry can never be used for Avodah. Rav Papa dispelled the proof for this according to R. Nechemyah. This is a better answer why the Rambam rules like R. Nechemyah: the Sugya in Avodah Zarah (also Zevachim 54a) is like him.

Minchas Chinuch (95 DH v'Nuchal): Alternatively, the Rambam holds that the Shamir was Batel after Bayis Rishon. Therefore, we must say that to build Bayis Sheni they smoothed the rocks outside using iron, like R. Nechemyah.

Answer #3 (Lechem Shamayim (Ya'avetz), brought in Likutim in Frankel Rambam): The Gemara in Avodah Zarah already said that we require Shalem rocks. There was no sincere Hava Amina that we can smooth them with iron. This was suggested merely to teach about "Lo Sanif". Likewise, we cannot use the Shamir because they must be Shalem. Perhaps the Shamir cuts smoothly enough!

Ramban (Shemos 25:7): The stones for the Choshen are called "Avnei Milu'im" because they were intact. The Shamir was needed for them. The stones for the (shoulders of the) Efod are not called Avnei Milu'im. The letters were carved into them. The Gemara said that the Shamir was needed for the Avnei Efod. It refers to the Avnei Choshen (the Choshen is attached to the Efod).

Question (Mishneh l'Melech Klei Makdish 9:7): Why didn't the Rambam mention using the Shamir for the stones of the Efod or Choshen?

Minchas Chinuch (95 DH v'Nuchal): The Rambam must have found a source that it is not essential (to write with the Shamir in order that the stones will be intact). He can hold that there was no Shamir in Bayis Sheni.