tiny diamonds in meteorite "signature of a long-lost planet": why come to Earth in 2008?
Many comets are such lucky ones...
That's why we see them with their icy tails evaporating: They have only recently been scattered into the inner solar system.
Just like the well-studied comet 67P, you could ask "where has 67P been for all those billion years?". For at least this comet, we know the answer: It has been orbiting in the outer solar system, until a close encounter in 1840 and a few subsequent later ones with Jupiter brought its' perihelion closer to the sun, where it started its' cometary activity.

I would place my bet on the origin of those comets being in the outer solar system, because:  


The nature article you cite mentions 20 GPa pressure, for which one needs at least a Mercury or Mars type body to generate. This is not necessarily a problem, because Mars-type bodies form quick and early (we know this from theory as well as data), within the first 3-5 Million years of the solar system, when gas is still there. This is about 10 times faster than an Earth-type body, which has 10 times the mass.
It is also thought that Mars-type bodies should form the basic building blocks for larger planets - thus there should be many more of them in the early solar system.
However even if there are many, now there are essentially none in the inner solar system - the asteroid belt contains roughly 0.1% of a Mars mass. The total mass of the Kuiper belt is estimated to be far larger, by factors of 10-100.
If a giant planet instability occurred, it requires a even much more massive Kuipter belt as trigger, after the gas disappears in the early solar system.


So, Summarizing: They're probably out there in the outer solar system, merrily orbiting along.