The Mishna quoted from Masechta Rosh HaShonoh says that after the problem of "Niskalkelu HaLeviim BeShir", witnesses were only accepted until "Mincha" (i.e. the Korban Tomid). The Mishna then says that if witnesses came after this time, the rest of the day was completed in Kedusha, as well as the following day.
(a) My question is: i.e. what happened at the time of Mincha - did they start doing Melocho at 3.30pm, and if witnesses came at 5.00pm then they stopped doing Melocho (to complete the day in Kedusha)?
(b) Furthermore, what do we mean by saying "if witnesses came..." -witnesses were always interrogated as to what they saw - wouldn't the Beis Bin just not interview them, so it would not be known if they saw the moon correctly or not, and there would not be a question of "if witnesses came..."?!
(My vague recollection from when I learnt that Mishna was that once the time of Mincha came, they continued the Issur Melocho regardless, but this does not fit with the text of the Mishna)
(a) Apparently, there would be reason for them to stop observing the Isur Melachah, because even if witnesses come on that day (after Minchah), that day does not become Kadosh mid'Oraisa retroactively, but rather the following day is declared as Kadosh (and the day on which the witnesses came is only Kadosh mid'Rabanan). Consequently, at the time of Minchah there is a Safek d'Rabanan whether or not witnesses will come (requiring that the day be Asur b'Melachah mid'Rabanan), and if so they could start doing Melachah at Minchah (Safek d'Rabanan l'Hakel), and stop doing Melachah if witnesses come later.
However, Rashi (DH Ad ha'Minchah) says, "They complete that day with Kedushah," implying that Melachah does not become permitted at all, even when the witnesses do not come by the time of Minchah. The words of the Mishnah which you cite are not a proof either way, because perhaps the Mishnah mentions that witnesses came "after Minchah" in order to teach that even though witnesses came today, nevertheless the next day is Kadosh.
This is also clear from Rashi in Rosh Hashanah 30b, and from the Ritva in Eruvin 39b, who write that they observed that day as Kadosh in order to prevent that day from being treated disrespectfully (see Gemara Eruvin 39b), lest people say "last year we refrained from Melachah in vain, so this year we will do Melachah." If this is the reason, it would seem that the Rabanan decreed that the day be observed as if it was definitely Kadosh even if witnesses do not come at all.
The Ran here writes that since most of the day has been observed as Kadosh, we complete the day with Kedushah (see also the words of Rashi here). According to the Ran, also, it must be that they always observed that day as Kadosh. However, the Rambam (Hilchos Kidush ha'Chodesh 3:6) implies that only when witnesses came did they observe the day as definitely Kadosh.
(b) That was part of the Takanah of Raban Yochanan ben Zakai -- not to interview the witnesses. (They knew that witnesses had come to testify about the moon, though. They just did not interrogate them.)