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](https://web.archive.org/web/20150703041454/http://www.crowdsourcing.org/editorial/a-brief-history-of-crowdsourcing-infographic/12532), which says that 800 volunteers contributed to the first fascicle alone.)

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