The gemara implies that the shamir worm was needed for the avnei eifod to carve out the name of the shevatim, as rashi explains based on sotah. Tosafos proves that the shamir must have existed in the time of the bayis sheini becasue in the story with dama ben nesina they needed the eifod stones, and that story took place in the second tempe era [from the fact that they had a para aduma]. The eifod stones would be useless without the shamir, since there was no other way to carve on the stones, which implies that they had access to the shamir in the second beis hamikdash. Although Shlomo had a hard time accessing the shamir, Tosafos assumes that they kept it from the time of Shlomo through the destruction of the bayis sheini.
The Ramban in Chumash in Parshas Teruma (cited by rashash) says that only the avnei choshen needed a shamir because it says "במלואתם", but the avnei eifod to not need a shamir [and the gemara which says avnei eifod is not precise] and can be scratched with a knife. Based on this, we no longer are able to prove from the story of dama ben nesina that there was a shamir in the second beis hamikdash, since the stones they needed were not choshen stoner, just eifod stones. Based on this, the Minchas Chinuch (mitzvah 95) suggests that there is a machlokes in sotah 48b if the shamir was needed for the stones of the beis hamikdash. Although the gemara implies that we pasken like R' Yehuda that we need the shamir for the beis hamikdash stones, the Rambam paskens like R' Nechemia that the shamir wasn't needed [rather they used knives to cut the stones outside of the har habayis area]. The Minchas Chinuch is bothered by what compels the Rambam to pasken like R' Nechemia that they didn't need a shamir. He suggests that the Rambam held like the Ramban and therefore there is not gemara compelling that the shamir existed in the second beis hamikdash. Since they were able to build the second beis hamikdash even in the absence of a shamir, it must be that we pasken like R' Nechemia that the stones could be cut with metal knives so long as it is outside the area of the mikdash.