For several significant textual variants -- Mark 16:9-20, John 7:53-8:11, and Luke 22:43-44, for example -- solutions have been proposed which involve the idea that the unusual treatment of these passages in early lection-cycles contributed to their loss in part of the transmission-stream. Some other variants, such as the non-inclusion of John 9:38-39a in some early witnesses -- have also been accounted for as having been elicited by special factors involving the presentation of the passage in a lector's copy. (A lector was the person entrusted with the task of reading Scripture in early Christian worship-services.) The usual, almost predictable, answer to such theories has been along the lines that the lectionary did not develop early enough to have such a strong impact on the text of the Gospels.
However, one would not need a fully developed annual cycle of lections for every day of the year in order to account for a few significant losses. The annual observances of major feast-days -- Easter-week, Pentecost, Christmas, Ascension-Day, and memorials of the apostles and a few martyrs -- are all that would be necessary. There is nothing implausible about the idea that regular annual observance of major feast-days was already customary in the mid-100s.
In 1900, a researcher named Charles Taylor published some finds from the Cairo Genizah (a fascinating subject for its own sake, but that's not our main subject today). The manuscripts that he published included fragments of a Greek lectionary, containing text from Matthew 10 (and part of the lection's title) and John 20. The production-date of this manuscript was assigned to the 500s, making it one of the earliest lectionaries (or, fragments from a lectionary, at least) known to exist.
Taylor's lectionary -- lectionary 1276 -- is a palimpsest; that is, it consists of recycled pages. Someone who needed parchment obtained pages from a Greek lectionary, washed off the lettering, and reused the parchment to write a Hebrew composition. (Whoever this person was, he also obtained pages from a copy of Acts and First Peter -- other pages of the Hebrew composition are palimpsests with text from those books underneath the Hebrew lettering; those pages constitute the uncial manuscript 093, which Taylor also published.) Centuries later, part of the Greek lettering, which was not entirely washed away, remains legible.
This picture of the fragments of Lectionary 1276 is based on the plates in Charles Taylor's book, Cairo Genizah Palimpsests. The presentation of these fragments begins on page 89 (digital page-number 104).