While reading Saint Aldhelm's 'Riddles' I saw a reference to Lucan's Orpheus, a Latin poem written in the first century AD. The seventh century writer Aldhelm had a copy of Orpheus, but it is now lost and survives only in quotations from his prose. Are there other ancient Latin works which are known to have survived into the Middle Ages or later, but are now lost?
Varro's Antiquities are probably the most famous example: they were quoted by Priscian (6c) — text in Keil's Grammatici Latini; the "Fasti of Ravenna" were quoted by the Anonymus Valesii, Agnellus (9c), and others (Hodgkin, Italy and Her Invaders, III.178). Cassiodorus had a copy of Seneca's Forma Mundi. Martin of Braga (6c) apparently had two of the younger Seneca's essays now lost. This is very quickly; I'm certainly missing a bunch of others.
Also (more narrowly interpreting your question), a number of Latin works have come down to us only in Syriac, Armenian, or Arabic translations (and I believe Ge'ez), so that we do not have the original Latin text, but the fact that there are translations in languages used later than the classical period is of course an indication that the Latin text many have existed at the time.