As per Matsya Purana Chapter 155-156, Adi was son of Asura Andhaka and to take revenge of his father, He went to Shiva's place knowing Parvati resolution of doing penance to become fare, he thought of killing Shiva, he passed Virbhadra(Who was guarding so that no one can enter Shiva's place) first being in the form of snake so that he won't be recognized by him and then he appeared in the form Parvati by putting on sharp and strong teeth in front of Shiva, but Shiva became suspicious about his presence because Adi's left area of ribs had no marks but bunch of hairs whereas Parvati has mark of Lotus. Knowing which Shiva hits his private part using Vajra-Astra by which he got killed immediately.
So if I understood correctly, it was not toothed vagina, but the teeth itself. I'll quote the exact text here:
afterwards in order to hide from virbhadra he transformed himself into a serpent and without being noticed by Virabhadra, crawled inside where diva was. Then, that great Asura, leaving off the disguise of the serpent, masquedered as Piirvatl in order to tempt diva. After making his form exquisitely alike l's rvati by his spell, he put on sharp and strong teeth, and made up his mind to kill Siva.