Rabbotai,
1) The Mishne mentions checking back several generations for a woman's yichus - 4 of her mothers and their mothers, going back to Great Great Grandmothers. What was the logistical method of doing this? This could cover a period of 150 years or so. Probably no one would be alive who would know a Great Great Grandmother. Did they have sifrei yuchsin? Was that enough?
2) Also the gemara talks about Moshe Rabbeinu's yichus - b'domeh lach, they should be similar in purity of family yichus to you. What constituted yichus before the Torah was given? Moshe Rabbeinu's father was married to his own aunt which would be a psul after the Torah would be given.
B'kavod,
Samuel Kosofsky
1) Checking Sifrei Yuchsin would probably be the way this was done, along with any other possible evidence. Remember, the Gemara's conclusion is that this Halachah only applies to families where there is some kind of rumor that there is a Psul in the family. Accordingly, one would have to check to ascertain that this is not so (see Aruch Hashulchan E.H. 2:8 at length).
2) As you pointed out, it obviously is not referring to Moshe Rabeinu's actual Yichus. It seems to me that it is referring to the fact that the person is not Pasul, which is usually a result of forbidden relations. This is why we find that a Mamzer is an Az Panim (see Rashbam in Bava Basra 58a, DH "Chabotu"), and the Shulchan Aruch (E.H. 2:2) says to stay away from families who are Azei Panim, as this is a Siman that they have Pasul Yichus. Moshe Rabeinu clearly was not an Az Panim, and this is the intent of the Derasha "b'Domim Lach."
All the best,
Yaakov Montrose