Medieval Wish List
Of course, this topic has already been dealt with extensively and magisterially by Simcha Emanuel, in his doctoral thesis Lost Halachic Books of the Tosafists. Hopefully, some day soon, it will appear as a book.
When I first started working with manuscripts, my friends - students of R Ezra Bick- requested the complete Talmudic commentary of R. David Bonfid. So far, I haven't been able to help with that.
Personally, I have long dreamt of the commentary of R Samson of Sens on Taharot coming to light in a medieval manuscript. The letter sent out by R. Ya'akov Sevara of Cracow - now that would be a find. I'll keep thinking. Feel free to contribute ideas.
How could I forget? More exciting (to me) than the first written Mishna, is the idea of a 7th century Talmud. Imagine finding the Talmud written by the mysterious Natronai, from memory, in Spain. And being able to compare it to, say, the version they were learning in Kairuan at the time.
Any talmudic or halachic material from pre-10th century Italy would be wonderful. Our main literary source for that period is Megillat Ahima'atz - a wonderful but not particularly historical document.