In the last perek of Menachos chazal assume that Chonyo (onias) was the son of Shimon Hatzadik who was chased out of Jerusalem in the time of the Second beis hamikdash because of an issue with his brother - one set up the other and resulted in chonyo being chased out) and erected a Temple in Alexandria, Egypt. Chazal debate whether Chonyo's intentions were l'sheim shamayim and the Temple was serving Hashem, or whether it was a hous of idolatry. Either way he was seriously misguided and doing an aveira so that chazal penalized all kohanim that worked in his Temple not allowing them to ever work in the Beis Hamikdash. Our gemara questions whether this penalty was only imposed on people or even on objects that were used in the Temple of Chonyo.
I found on wikipedia that Josephus writes that this Temple wasn't actually in Alexandria but rather in Leontopolis, Egypt. Chonyo supported and justified this Temple by citing pesukim in Yeshaya 19:18 indicating that there will be a Temple and miz'beiach in Mitzrayim on which sacrifices will be brought.
In the course of the sugya, the gemara introduces a concept of ובאו בה פריצים וחללוה which is actually a halachic concept that when the Greeks violated the Beis Hamikdash in the time of the Chashmonaim, they successfully removed the kedushas ha'makom of the mikdash. It is based on this concept that the stones of the miz'beiach actually obtained status of משמשי עבודה זרה. If the stones remaing "owned" by hekdesh, they couldn't actually become avoda zara because one cannot make into avoda zara something that is not theirs. But, since they successfully removed the kedusha status and the mizbeiach became chulin, they were able to acquire it and turn it into משמשי עבודה זרה. The Ritva in Makos 19a says that the opinion that the gemara mentions in many places about the kedushas yerushalayim being nullified is based on this concept of באו בה פריצים וחללוה. The Ritva understands that they had the ability to not only remove kedusha from the stones of the mizbeiach but even from the city of Jerusalem. The Chasam Sofer (Y.D. 233) and Ohr Sameiach use this concept to explain why we mourn on the 9th of Av rather than the 10th, since R. Yochanan says that most of the mikdash burned on the 10th. The answer is that the first moment that it was lit was the point that the kedusha left because באו בה פריצים וחללוה, so that is what we mourn.
The gemara continues by saying that the chachamim weren't sure what to do with the stones of the mizbeiach. One suggestion was to break them in order to be mevatel them (rashi), to which the gemara says that it was forbidden to use stones that weren't perfectly smooth. The gemara implies that it is impossible to be mevatel avoda zara without physically breaking it, otherwise that would have been a good suggestion. However, the Rama (y.d. 146:7) writes in the name of the Mordechai that bitul can be achieved by speech without actually physically damaging the avoda zara. The mekor mayim chaim (side of shulchan aruch) asks from our sugya and explains that a goy can be mevatel by mere speech, but a Jew can only force a goy to be mevatel if the goy actually breaks it. It is clear from the gemara 44b that one doesn't need to physically damage the avoda zara in order to be mevatel it, because the gemara says that if one would urinate in front of it b'kvius, it would also serve as a bitul. But, the gemara implies that an action would be necessary - although it could be that an action that is degrading such as setting it up as a place to urinate works as bitul automatically even without explicitly being mevatel it. Even the mishna 49b which implies that an action must be done to ruin it isn't conclusive because the mishna is trying to contrast the removal of pieces from the avoda zara for it's good which doesn't qualify as bitul. However, Rashi 42a d.h. she'pachsa, seems to hold that one must cause physical damage to the avoda zara to successfully be mevatel it (the gemara seems to require at least "pach'sa" which means to dent it, even when a goy is mevatel it).