The orchid A. sesquipedale has a spur so long that at the time of its discovery, no insect was known that could pollinate it.
This led Charles Darwin to predict the existence of an undiscovered moth based on the idea that the moth and the orchid had co-evolved. That moth, X. morgani praedicta, was subsequently discovered in 1903 – a triumph for early evolutionary biology.
Has it ever happened again that a species was predicted to exist before being discovered?
I'd imagine there would be numerous examples of this. One species I can think of is Monocercomonoides sp., before the discovery of which we didn't know any examples of eukaryotes that had completely lost their mitochondria, or the derived forms of these organelles, such as hydrogenosomes and mitosomes. A prediction wasn't necessarily coined by any particular person like in your example, although there might be some papers somewhere that make such a prediction, I'm sure many people hypothesised that it was probably possible for eukaryotes to completely lose mitochondria if their iron-sulfur cluster biogenesis pathway was replaced by a cytosolic system that could fulfil the same role but we didn't know of any that had.
See paper: http://dx.doi.org/10.1016/j.cub.2016.03.053
