Indeed, Yefei Einayim on Tosfos Sanhedrin 5a (printed at the back of the Gemara) cites the Midrash Rabah Bereishis 98:8 that a scroll containing details of lineage was found in Yerushalayim in which it was stated that Hillel was a descendant of David ha'Melech. (This statement also appears in Talmud Yerushalmi Ta'anis 4:2 p.40). This proves that R. Yehudah ha'Nasi (henceforth to be referred to as "Rebbi") was descended from Hillel, because Rebbi's father was Rebbi Shimon ben Gamliel, and Raban Gamliel was descended from Hillel, as were all of the Nasi'im after Hillel's time. (See also Bavli Horayos top 11b, that Rebbi was descended from Hillel.) The above therefore strengthens what you write that Rebbi was descended from David.

However, Yefei Einayim writes that according to Tosfos 5a - that the Nasi in Eretz Yisrael came from the female line - one is forced to say that Rebbi only descended from David on the maternal side. (It would appear to me that one can agree with Rashash on the above Midrash that Rebbi was paternally descended from Hillel - in contradiction to Yefei Einayim - but one must say that starting somewhere from Hillel and above, the descent from David was only maternal.)

According to this, one has to explain our Gemara - that Rebbi might be the Mashiach - to mean that it is sufficient that the Mashiach is descended from David on the maternal side, to qualify.

I can offer other examples where maternal pedigree is sufficient. Megilas Ester (2:5) states that Mordechai was a "Yehudi", but also a "Yemini". The Gemara Megilah, end 12b, asserts that the first title suggests that he was from the tribe of Yehudah, whilst the second suggests that he was from Binyamin. R. Yehoshua ben Levi resolved the contradiction by answering that Mordechai's father was from Binyamin but his mother from Yehudah. (Incidentally this means that Mordechai was of the same kind of lineage as Rebbe).

Rashbam (Bava Basra 91b DH Zeh) suggests from this that Yehoshua bin Nun's mother may have been from the tribe of Yehudah (even though Bamidbar 13:8 states that Yehoshua was the Nasi of the tribe of Ephrayim) and was threfore mentioned in Divrei ha'Yamim as being from the sons of Yehudah (see Rashbam there DH Mai).

See also Eruvin 41a that R. Elazar b'Rebbi Tzadok said that he was from the tribe of Binyamin. Tosfos DH mi'Bnei points out that R. Elazar was a Kohen, but nevertheless it is possible that his mother was from Binyamin (Tosfos Eruvin 63a DH Kol also mentions a similar idea).

We see from all of the above evidence, that matrilineal descent is also important, so it may be sufficient for the Mashiach to be descended from David from the female line alone.

(According to the above, possibly one has to say that the principle stated in Bava Basra 109b and elsewhere, that "the father's Mishpachah is considered Mishpachah, whilst the mother's Mishpachah is not considered Mishpachah", refers chiefly to questions of inheritance, but not necessarily to questions of predigree and descent).

D. Bloom