Does Eliyahu Hanavi come to every bris?

Since it was recently parashat Pinchas, and some sources associate Pinchas with Eliyahu Hanavi, I thought to discuss the midrash that Eliyahu Hanavi visits every bris, such that we have a kisei shel Eliyahu.

The earliest source I know of is Pirkei DeRabbi Eliezer, towards the end of chapter 29. There it reads:

"And so was Israel accustomed to circumcise,  until they were divided into two kingdoms, and the kingdom of Ephraim refrained from circumcising. And Eliyahu, zachur latov arose and with great kinah {zealousy / } and adjured the heavens not to rain down dew or rain upon the earth. And Izevel heard and sought to kill him. Eliyahu stood and prayed before Hashem. Hashem said to him, "Are you better than your ancestors? Esav sought to kill Yaakov, and he fled from before him and escaped, as is written 'And Yaakov fled to Sdei Aram.' Pharaoh sought to kill Moshe and he fled from before him and escaped, as is written 'And Moshe fled from before Pharaoh.' Shaul sought to kill David and he fled from before him and was saved, as it stated, 'And David fled and escaped.'

This to teach you that whoever flees escapes {and is saved}. And Eliyah arose and fled from the land of Israel (and escaped), as is written 'And he got up and he ate and he drank, etc.' Hashem appeared to him and said to him, 'What are you doing here Eliyahu?' He said to Him, 'I was zealous'. Hashem said to him, "You have always been zealous! You were zealous in Shittim regarding illicit relations {regarding killing of Zimri}, as is stated, 'Pinchas ben Eleazar, etc.' And here you are zealous! By your life, Israel will only do Bris Milah while you watch it with your own eyes!'

From here, our Sages instituted that there would be an honorable seat for the Angel of the Bris, as is written {Malachi 3:1}:

א  הִנְנִי שֹׁלֵחַ מַלְאָכִי, וּפִנָּה-דֶרֶךְ לְפָנָי; וּפִתְאֹם יָבוֹא אֶל-הֵיכָלוֹ הָאָדוֹן אֲשֶׁר-אַתֶּם מְבַקְשִׁים, וּמַלְאַךְ הַבְּרִית אֲשֶׁר-אַתֶּם חֲפֵצִים הִנֵּה-בָא--אָמַר,ה צְבָאוֹת.

1 Behold, I send My messenger, and he shall clear the way before Me; and the Lord, whom ye seek, will suddenly come to His temple, and the messenger of the covenant, whom ye delight in, behold, he cometh, saith the LORD of hosts.

May the God of Israel rapidly bring, in our lifetimes, Mashiach to console us, and to renew our hearts, as it written 'and return the heart of fathers unto the sons.'"

Now, Pirkei deRabbi Eliezer is post-Talmudic, from about the 9th century. It is also found in Shir HaShirim Rabba, which is also about that early, and in Zohar, which is much later. I don't know of any early source -- that is, from the Tannaim or Amoraim -- which makes this claim.

There is an obvious problem with Eliyahu Hanavi coming to every Bris. And that is that in the gemara in Eruvin, which I have been discussing lately, they try to prove that there is no techum higher than ten tefachim. And they attempt proof from Eliyahu being in Sura and later that Shabbos afternoon, in Pumpedisa, which was extremely far off, as well as past the techum. They reject this because maybe it was not Eliyahu Hanavi but Yosef the Sheid who delivered the message from Sura. And in the same gemara they try to prove it from Mashiach not being able to come on Shabbos, and so on and so forth.

Now, if Eliyahu must visit every seder, and there has been at least two brissim which co-occured on Shabbos or across Yom Tov, distant from one another, then Eliyahu would need to visit both. And given the number of Jews throughout history, in disparate places, this must certainly have happened at least once! If so, the gemara should have brought this as a proof. That it did not is evidence, to me at least, that they did not know about this belief. (Yes, we can always make teirutzim; e.g. Eliyahu sends a spark of himself; or as "angel" is not subject to halacha, which he is when clothed in human form; or he has elves -- though the latter only really works for Eliyahu at the seder table.)