An early editor, Antonio Agustin, in his preface to his edition of 1559, describes the transmission as follows:
In these twenty books, which he entitled de verborum significatione, or priscorum verborum cum exemplis, Sextus Pompeius Festus abridged the books of Verrius Flaccus on the same subject. For he omitted the words which were, in Verrius’ own words, ‘too old, and dead and buried and were of no use and authority’. He dealt with the same words [that Verrius had discussed] more clearly and more briefly, setting out the original words in a smaller space. He also provided a critical treatment of examples found in other sources. He often corrected Verrius’ errors, and he always explained most learnedly why he did so.
Now this book had the misfortune to suffer harm of several kinds very long ago. For we could not find out either who this Festus was, or when he wrote this work. Only one or two references to it are to be found here and there in Charisius and Macrobius.
While the whole book was still extant in the time of Charlemagne, one Paulus thought it would be useful if he made a sort of epitome of the parts he liked best. Ignorant men liked his book so much that it took Festus’ place in every library.
One codex survived the slaughter. But that was like a soldier whose comrades have been defeated and massacred, and who creeps along at random with his legs broken, his nose mutilated, one eye gouged out, and one arm broken. This book supposedly came from Illyria. According to Pio and Poliziano, Pomponio Leto had some pages of it; Manilius Rallus had the greater part. Angelo Poliziano received the book from them, went over it, and copied it, and he tried to use it in his Miscellanea to emend a verse of Catullus. Using this same copy by Poliziano, Pier Vettori has begun, with his customary learning, to emend the vulgate text of Festus at various points in his Variae lectiones.
The remains of the codex passed to Aldo Manuzio, who tried to combine them with the epitome of Paulus, thus making one body from two sets of parts. But so much was omitted [or] changed in publication that it was still necessary for other critics to intervene. Achille Maffei, the brother of Cardinal Bernardino, has another copy, similarly confIated from both texts; it is fuller than the Aldine. Thus there have been three recensions of the same text, all imperfect. There is the old MS of half of Festus; of this, nothing remains before the letter M, and from that letter to the end barely half of what there used to be. The second text is Paulus’s epitome. As we show in this edition, even the most ignorant can see from a comparison of the texts how carelessly that was put together. The third text is that conflated from the other two, like those of Aldo and Maffei, and our own.
Stirring stuff! Anthony Grafton, who translated the Latin  rightly remarks, “by no one has [the story] ever been told in livelier terms”.
Grafton corrects the picture slightly. Various editions of the epitome by Paul the Deacon started to appear in print from 1471 onwards. The solitary codex to survive the Middle Ages is Naples, Bibliotheca Nazionale IV.A.3, written in the second half of the eleventh century, probably at Rome. It originally contained sixteen gatherings, the first seven of which had already been lost by the time that it reappeared in the fifteenth century. He continues:
The nine that remained had also been damaged by fire, so that some leaves were missing, and on many leaves most or all of the outer column of the text was also lost. Manilius Rallus, a Greek from Sparta who became a successful Roman Catholic churchman and Neo-Latin poet, brought it to Italy at some time before 1477. He is said to have found it in Dalmatia.
Rallus lent this codex to Pomponio Leto, who found it most helpful for his pioneering research into Roman antiquities. He drew on the new codex for his university lectures on Varro and other authors. Unfortunately, he treated the codex with his usual lack of scruple – he kept the eighth, tenth, and sixteenth gatherings, which have subsequently disappeared, and must be reconstructed from a number of surviving transcripts.
These statements about the ms. Grafton references to the edition of W. M. Lindsay (1913), p.iii-xi (the statements about Leto are from elsewhere).
However Fay Glinister disagrees on one important point:
When the manuscript surfaced, some time before the death of the humanist and philosopher Lorenzo Valla (1406-1457), it was already incomplete.
 For the date, see Lorenzo Valla, Le postille al”Institutio oratoria’ di Quintiliano, eds. L. Cesarini Martinelli and A. Perosa (Padua 1996). There had previously been a claim that the MS was found in Dalmatia in the 1470s, by the Greek Manilius Rhallus; it is now evident that this was a mistake.
I presume from this hasty reference that there is evidence that Valla referred to Festus (and not to the epitome of Paul the Deacon), but without access to the Valla text, it is not clear what the argument is.
Lindsay on the other hand tells us:
In Illyrico codicem repertum fama erat, sed non satis certa.
It is supposed that the codex was found in Illyria, but this is not quite certain.
No reference is given for this statement. Rhallus’ claim to discovery is based on his edition of the epitome by Paul the Deacon in 1471, in which he refers in the preface:
Nuper cum legissem Pompei Festi mutilatos libros qui priscorum verborum inscribuntur, vehementer dolui quod tantum opus integrum non remansit.
Recently when I read the mutilated books of Pompeius Festus which are inscribed priscorum verborum, I greatly regretted that such a work should not be preserved complete.
But whether this refers to the manuscript, or to the epitome is not clear.
The Illyria story seems to derive from the preface of the editio princeps, 1500, at Milan, from Io. Angelus Seinzenzeler, which contained Nonius, Festus with Paul the Deacon, and Varro. The editor was Io. Baptista Pius. In his preface he writes:
His quae nobis venerunt ex codice pervetusto et ob hoc fidelissimo, qui ex Illyrico Pomponio Laeto fuerat oblatus, …
These things, which came to us from a very old and therefore very reliable codex, which was brought from Illyria by Pomponio Leto, …
There are no other references to a find in Illyria in Lindsay. It would be good to clarify precisely what is, and is not, known about the circumstances of the rediscovery.