Gemara

(Ula): All agree that the tongue is considered internal regarding Tevilah (immersion). "He will wash his flesh in water" - what is external, like his flesh.

Question: Rebbi is concerned for inside the mouth!

(Ravin): A Shifchah of Rebbi's house once found a bone between her teeth after immersing. Rebbi required her to immerse again.

Answer: Water need not enter the inside of the mouth, but it must be fitting for immersion, like R. Zeira's law.

(R. Zeira): If a flour-offering is small enough that it could be mixed (with the proper amount of oil in the Kli), even if it was not kneaded, it is Kosher. If it is so large that it cannot be kneaded, it is invalid because it was not kneaded.

Chulin 10a (Beraisa): If a Tamei immersed, and later found a Chatzitzah (obstruction) on his body, even if he was working the whole day (after Tevilah) with that substance (of the Chatzitzah), the Tevilah is invalid, unless he is sure that there was no Chatzitzah when he immersed.

Since he was known to be Tamei, we leave him in his Chazakah.

105a (Rav Chisda): If one ate meat, he may not eat cheese (right away). If one ate cheese, he may eat meat.

Rishonim

Rambam (Hilchos Mikva'os 2:13): If a Nidah found a bone between her teeth (after immersing), it is as if she did not immerse.

Rosh (Hilchos Mikva'os (b'Sof Nidah) 35): She must clean her teeth so there will be no Chatzitzah there.

Tosfos (25b Sof DH Kol): "Kol Besaro" teaches that Beis ha'Starim (a covered place) must be clear so water could get there.

Zichron Yosef (brought in Shiyurei Taharah YD 198:23 DH u'Midei): How can we expound about Beis ha'Starim? It is the minority of the body. Mid'Oraisa, only a majority that one cares about is Chotzetz! A Chatzitzah is different. If it is the minority, or he does not care about it, it is like his flesh. If one clenched his lips or hands and did not let water enter, mid'Oraisa this is not Tevilah.

Rebuttal (Shiyurei Taharah, ibid.): Also clenching lips or hands disqualifies due to Chatzitzah. The Rambam does not disqualify mid'Oraisa if all the hair is knotted. He must say that the Drashah about hair teaches that it can join to comprise a Chatzitzah on the majority. The same applies to Beis ha'Starim. The Ritva holds that the Drashah for Beis ha'Starim is only mid'Rabanan.

Poskim

Shulchan Aruch (YD 198:24): She must clean her teeth, so there will be no Chatzitzah in them. If she immersed and found something stuck to them, the Tevilah was invalid.

Beis Yosef (DH Tzerichah): Semag says that the same applies if meat or crumbs were found between her teeth, or anything else, like the Tur says. R. Shimshon says that Rebbi's Shifchah was married, therefore she was particular about Beis ha'Starim, lest her husband despise her. (Note: slaves have no Kidushin. One can designate a slave for her, similar to Shifchah Charufah). Alternatively, any woman is particular about a bone between her teeth. It is b'Din (correct) to clean her teeth from Chatzitzos, like the Rosh says, for remnants of food are often found between teeth.

Bach (DH v'Im): Chachamim did not obligate her to clean her teeth. The Gemara merely says that if something was found afterwards, she must immerse again! It seems that the Shulchan Aruch means that it is advantageous for her to do so, for if not, if she finds something she must immerse again. The Terumas ha'Deshen (184) says that we make such inferences from this wording.

Rebuttal (Shach 30): The Terumas ha'Deshen said so only regarding checking the knife between Shechitos, lest he find a nick in the knife at the end, and all the animals will be Safek Neveilos. If it were obligatory to check after each Shechitah, lest one eat from an animal before he checks after finishing to slaughter, the Gemara would have said so. Here, even if it is obligatory, the reason is (like the Gemara said) lest there is a Chatzitzah, for a woman need not check herself after Tevilah. The Beis Yosef explains that it is obligatory, for remnants of food are often found between teeth. Also the Levush says 'she must check, and if afterwards she found...' (i.e. checking is not merely good advice, lest she find a Chatzitzah). She may not say 'I will check after Tevilah', lest she forget to check.

Shulchan Aruch (ibid.): Some women have the custom not to eat meat on the day before going to the Mikveh, for it enters between the teeth more than other foods. Even though they check and clean the teeth, they are concerned lest they be unaware of something that remains. This is a good custom.

Beis Yosef (ibid.): This is a good custom. Also R. Yerucham praised it.

Taz (25): Clearly, if she ate meat that day, she need not postpone Tevilah due to this. The custom is to eat meat on Shabbos and Yom Tov, just she must dig out pieces left between her teeth very much afterwards.

Gra (22): One may not eat cheese (right) after meat, even though one may eat meat after cheese. The Rambam (Ma'achalos Asuros 9:28) and Shulchan Aruch (YD 89:1) say that we are concerned for meat between the teeth.

Rema: She should not eat between bathing and immersing.

Source (Rosh, Kitzur Hilchos Nidah, after Hilchos Mikva'os, cited in Beis Yosef (ibid.): It is a good custom not to taste anything between bathing and immersing, so there will be no Chatzitzah between her teeth.

Shulchan Aruch (26): If she did not check between her teeth beforehand, nor afterwards until she ate, and she found a bone between her teeth, we are lenient and assume that it came later.

Source (Ba'al ha'Nefesh Sha'ar ha'Tevilah Siman 2, cited in Beis Yosef DH Kosav ha'Ra'avad): Rebbi disqualified his Shifchah's Tevilah only because she found a bone. If she found it after eating, presumably we are lenient and say that it came later, since we do not require that water enter the mouth.

Question (R. Akiva Eiger on Shach 32 and Gra 199:27): In Sa'if 25, we are lenient if Beis ha'Starim (places that are normally covered) were checked only after Tevilah. Here, since something was found, it is as if it was not checked! This leniency requires investigation.

Shach (33): The Roke'ach disagrees. If a Tamei immersed, and later found a Chatzitzah, even if he was working the whole day with that substance, the Tevilah is invalid (Chulin 10a). One should be stringent.

Sidrei Taharah (Shiyurei Taharah 51): Sometimes we are stringent about a Safek mid'Rabanan, i.e. a Chatzitzah on the minority of the body.

Machatzis ha'Shekel (DH v'Yesh): Regarding one who did not check before or after Tevilah (Sa'if 25), the Shach said that we are lenient about a place where water need not go. The Roke'ach is no more lenient about such places, so one should be stringent also there.

Beis Lechem Yehudah (16): L'Chatchilah, we are stringent. B'Di'eved, she is permitted. If the night passed, she need not immerse.