@Lamdan the mishna in R"h 20a (not sure I got that right) discusses a story of 40 pairs who stopped by at one of the tanoomin on their way to be meid on the same shabbos. In that case it will be very hard to assume there weren't eideim about the chillul shabbos.
@dirah, the Kheloy Yaakov in R'H siman 20 proves eidues shey ata yachol lehazeima is meacev also in kiddush hachodesh, from tosfos in Kesovos 20a that explains the halacha of ein ed naasa dayan is because that way it is eidus shey ata yachol lehazima. Since ein eid naasa dayan also in kiddush hachodesh, we see from tosfos eidua shey ata yachol lehazima is passul by kiddush hachodes.
Also what u quote from R Shmuel that eidus shey ata yachol lehazima is based on being mevatel there eidus, is basically a rashi in Sanhderin 40a. However, this would still not answer the rebbes question, as in his case the eidus would not be void due to the eidim being muzamim, rather due to them being passul leidus.
Even though we used hazomo to arrive at that conclusion, since we now know they are not eidem at all, they are eidem zommim, and the process was thus not a genuine hazomo. So even according to Rashis opinion it is lechorah an eidus shey ata yachol lehzsima.
Standing on Lamdan's pshat, I think the answer is that even if there are other eidem to prove the chilul shabbos, the eidem are innocent until proven guilty. Thus, we can be mekabel their eidus on the assumption of being meizem them. (Ein adam karov etzel atzomo, so we don't trust them about coming on shabbos).
Even if later eidem came to testify that they came to BD on shabbos, the eidus would remain acceptable as at the time of eidus it was kosher and roy lehzama. The only problem would be if we first accepted the testimony of those who say the eidem came on shabbos.
That would be impossible, as so long as we don't have eidi hazomo, we assume they are honest, and thus coming on shabbos is not chillul shabbos. Hence the testimony about their travelling on shabbos serves no purpose (as they remain kosher), and from the sugya of chetzi davar we know that we don't hear eidus without practical implications.