I agree with your assumption that the date of the earliest recorded usage of a word does not necessarily correspond to the earliest usage of a word, since words may have been in circulation in spoken language before they were first used in publications, and many old publications have simply not survived.

Before there were digital corpora and digital texts, lexicographers had to read physical books to find usage examples. The editors of the first edition of the Oxford English Dictionary (which started their work in 1857 or 1858) asked thousands of volunteer readers to submit usage examples, in what was an early example of crowdsourcing. (See the crowdsourcing timeline, which says that 800 volunteers contributed to the first fascicle alone.)

In short, finding early usage examples required a lot of reading.

I agree with your assumption that the date of the earliest recorded usage of a word does not necessarily correspond to the earliest usage of a word, since words may have been in circulation in spoken language before they were first used in publications, and many old publications have simply not survived. I touched upon this issue in my answer to the question How many of Shakespeare's words in his plays were new? on Literature Stack Exchange: a number of words that are first attested in Shakespeare's plays may have circulated earlier, either in the spoken language or in writings that have not survived (or both).

Before there were digital corpora and digital texts, lexicographers had to read physical books to find usage examples. The editors of the first edition of the Oxford English Dictionary (which started their work in 1857 or 1858) asked thousands of volunteer readers to submit usage examples, in what was an early example of crowdsourcing. (See the crowdsourcing timeline, which says that 800 volunteers contributed to the first fascicle alone.)

See also the description of the OED's Reading Programme. James A. H. Murray set this up in 1879; its focus was not specifically on finding the earliest examples of words and phrases. In addition, the first edition "relied heavily on a small number of authors (notably, of course, Shakespeare) for its coverage of Early Modern English (1500-1700)". This selection was possibly too narrow to find the earliest surviving examples of words and phrases. For this reason, the current Historical Reading Programme looks at a broader spectrum of texts:

Today, readers systematically survey a much broader spectrum of texts from this and other periods. A separate Historical Reading Programme has been created to serve this function. Readers participating in this programme supply material specifically for the revision of the OED; usually these are earlier examples of words or phrases that are already included in the Dictionary. These readers check their findings against the Oxford English Dictionary to ensure that only significant items are filed, such as earlier examples of words and meanings or terms that have not yet been registered in the database.

In short, before the digital era, finding early usage examples required a lot of reading.