I first encountered the missing link in 1863 in a book called Man; or, The Old and New Philosophy by Rev. B.W. Saville. I have never heard of Rev. B.W. Saville, but here's what he had to say,
It is a continued source of lament among the savants of the present day that there is no sign of the missing link, even in a fossil state, between Pithecus and Homo, whether it be Adam or his first human grandpapa. We venture to think that we have discovered some notice of the said missing link, and if our find should prove true, we may fairly claim admission to the first class of discoverers, such as Roger Bacon, Flavio Gioja, Laurentius Coster, Galileo, Isaac Newton, James Watt, and others who have adorned and benefited the human race. We ask their attention to the writings of one Sanconiatho, an ancient Phoenician historian, who flourished B.C. 1280, about three centuries after Moses, as we find this ancient speaking of certain animals which once existed on earth, and which he declares were formed from the "fermented watery substance or Mot, which was void of sensation (anti-aesthetic, we presume). From these were generated intelligent beings called Zophasemin, or star-gazers (ancestors of the Galileos and Herschels and Lord Rosses of modern times), and they were formed in the shape of an egg. These for some time lay in a dormant state, until they were drawn up by the heat of the sun into the air, where they were dashed against each other, thunder and lightning being the result; at which noise the beforementioned intelligent animals awoke (like Lord Byron in later days) and found themselves famous, and began to move about by land and sea, male and female." Eusebius, to whom we are indebted for having preserved this valuable fragment of Sanconiatho, justly observes that "these things were found written in the Cosmogony of Thoth, and were drawn from his observations and the natural signs which by his penetration he perceived and discovered, and with which he has enlightened our minds." We may now safely assume that intelligent Motites constitute the long sought for link between man and beast.Uh, yeah. OK. Let's move on to someone who actually makes sense.
Next I found two references from 1867. The first appeared in a section of the Ethnological Journal titled "Memoirs read before the Anthropological Society of London." There we read this passage (which sounds eerily familiar):
The eighth paper is by Dr. Joseph Barnard Davis, and it is on the " Neanderthal Skull; its Peculiar Conformation Explained Anatomically." If any man living knows all the uses to which skulls, ancient and modern, can be put, excepting drinking strong ale out of them, it is Mr. Davis; for he has lived many years in a kind of domestic Golgotha - described, delineated, and engraved the skulls of all the races of man ; so that for whatever a skull may be worth Dr. Davis is the best authority. When the now famous Neanderthal skull - or, rather, the fragment of a skull - was first discovered, the advocates of the Darwinian theory of transmutation hoped they had found the missing link between man and monkey; but, unluckily for the hypothesis, the fragment in question turns out to be abnormal, or, in other words, part of a malconformed human cranium, very possibly of an unhappy idiot. Dr. Davis proves this anatomically; and so the missing link is still a desideratum.(NOTE TO READERS: I do not agree with the section I just quoted. Just so you know. Neanderthals are definitely not malformed modern humans.) Neanderthal was also discussed as a "missing link" at the September, 1865 meeting of the British Association for the Advancement of Science (published by John Murray in 1866), although less sensationally.
In the 1867 Transactions of the Ethnological Society of London, we find a paper titled "Archaeology and ethnology: remarks on some of the bearings of archaeology upon certain ethnological problems and researches" by Robert Dunn. He remarks, "Need I here remark that 'the missing link' is still wanting, and that, as I opine, it never will be found." Finally, in the 1869 Anthropological Review, the missing link is mentioned three times, all of which are also unfavorable.
Based on this preposterously incomplete sample, it would seem that the "missing link" was more frequently used by early critics of evolution than by advocates. Perhaps that's why each new Australopithecus (like sediba) is trumpeted as "the missing link:" people still subconsciously smarting from these early critiques that have been perpetuated even by modern critics of evolution? I don't know. That's just pure speculation for a Tuesday morning. Take it for what you will.
But it would make an interesting research project for a historian of science.