1) The Maharsha writes indeed that what Rashi (100b, DH Ela Lav) wrote -- that both fathers had Znus with her -- is Lav Davka. It could also be that the first had Znus and the second married her since, anyway, the child will be Kasher. This is because the Halachah does not follow Rebbi Elazar who stated above (59b) that a single man who had relations with a single woman thereby rendered her a Zonah. Therefore, the second Kohen was allowed to marry her.

2) The Perishah on the Tur (EH 3:10) writes that if she would have had Znus with the first and then married the second, we would assume that the father is the second because of the rule (Sotah 27a) that the majority of Be'ilos are with the husband. The Chelkas Mechokek on Shulchan Aruch (EH 3:12) also understands Rashi literally, because if she would have married the second one we would assume the baby was born from the marriage. This is why Rashi wrote that they were both with Znus, since it is only then that there is an equal Safek about who is the father.

3) Here is the answer of the Aruch la'Ner:

a) The Aruch la'Ner here gives another reason for why Rashi wrote that they were both with Znus. This is based on the Gemara above (35a) that says that with Znus, the woman turns herself over at the time of Tashmish to avoid becoming pregnant. Therefore, there is more likelihood of a woman becoming pregnant during marriage than through Znus, so if she had married the second one we would assume that he was surely the father, and the child would be allowed to be Metamei for him since he is Vadai the son of the second. Now that Rashi writes that there was Znus with both, it follows that neither is more likely than the other to be the father.

b) The Aruch la'Ner writes that even though Rebbi Yehudah disagrees with Rebbi Yosi (above, 35a), still Rashi prefers to explain in a way that is consistent with all opinions. In addition, the Halachah follows Rebbi Yosi, so Rashi explains according to his opinion. Furthermore, the Gemara above (35a) explains that Rebbi Yehudah disagrees with Rebbi Yosi because he is concerned that possibly she did not turn over well. A married woman does not turn over at all, so this means that in Znus it is doubtful whether she turned over well, but in marriage she certainly did not turn over, so Rebbi Yehudah will agree that most times the baby is from the husband. Therefore, even according to Rebbi Yehudah, Rashi needed to write that it was Znus with both of them in order for it to be an equal Safek.

c) We can say that the Aruch la'Ner agrees with the Perishah and Chelkas Mechokek, cited above, that it is most likely that the proper husband is the father, but for a different reason. They explain, based on Sotah 27a, that most Be'ilos are by the husband, while the Aruch la'Ner explains, based on Yevamos 35a, that in Znus the woman makes a special effort not to become pregnant.

4) The answer of the Beis Shmuel:

The Beis Shmuel (on Shulchan Aruch EH 3:16) cites the Maharsha that Rashi is Lav Davka, but then he cites the Perishah and the Chelkas Mechokek, whom I cited in my first reply, who understood that Rashi is b'Davka because if the second man married her we would say that most Be'ilos are from the husband. The Beis Shmuel continues and comments on the Diyuk of the Perishah and the Chelkas Mechokek from Rashi. He writes that if you want to say that Rashi b'Davka wrote that they were both with Znus (not like the Maharsha), then one can say that Rashi wrote this only according to the Makshan, the opinion in the Gemara that was asking a question on Shmuel. Shmuel said that if one of ten Kohanim had relations with a woman, the baby is a Shtuki inasmuch as we do not consider him to be a full Kohen since we do not know who the father is. The Gemara questioned Shmuel from the Seifa of the Mishnah where we do not know if the father is the first man or the second man. Rashi is pointing out that it may be that if one of the ten Kohanim married this woman and another of the ten Kohanim had Znus with her, Shmuel might say that the baby is a full-fledged Kohen because we assume his father is the husband. Since Shmuel may be referring spcifically to a scenario where only Znus is involved, it follows that one can ask a question on him only from a source where only Znus is involved. This is why Rashi wrote that both did Znus.

5) Support for the Aruch la'Ner from Rashi (Yevamos 69b, DH Aval b'Znus):

a) In my reply above I wrote in the name of the Aruch la'Ner that if there was Znus with the first man, and she was married to the second man, the fact that she turns over in Znus to avoid becoming pregnant (as stated in Yevamos 35a) means that we consider the husband to be the certain father. In fact, the Aruch la'Ner adds there, "Leika Safek b'Rishon" -- there exists no doubt that the child might be from the first, since the first one was with Znus.

b) I found support for the Aruch la'Ner from Rashi above (69b, DH Aval b'Znus). The Gemara (Yevamos 69b, seventh wide line) states "b'Nisu'in Chasheshu b'Znus Lo Chasheshu" -- there is a concern that a married woman became pregnant, but there is no concern that a woman becomes pregnant from Znus. This Gemara itself seems to be support for the simple reading of Rashi (100b, DH Ela Lav, unlike the Maharsha) that it is only if they both had Znus with her that we say that the child might be the son of either man, with the implication that if the second one was the husband, there is no reason to be concerned that the first could be the father. Rashi (69b, DH Aval) strengthens this by writing that the reason we are not concerned that she became pregnant through Znus is because we rule that in Znus she turns over to prevent conception. Rashi concludes, "Hilkach Leika Safek" -- there is no Safek. (It seems that this is the source of the words of the Aruch la'Ner, "Leika Safek b'Rishon.") Through Znus, a woman does not become pregnant.

c) Now we understand why Rashi (100b) writes that they both had Znus with her. Clearly, if a single woman became pregnant, we see that Rebbi Yosi's rule -- that a woman who has Znus turns herself over -- does not hold in this case, since we see that she conceived. What Rebbi Yosi means is that it is unusual for a woman to become pregnant through Znus. Therefore, Rashi implies that if the first man had Znus and the second man is a proper husband, the husband is certainly the father.

Kol Tuv,

Dovid Bloom