The only proof we have seen so far, indicates that the ability re-spawns immediately, as can be seen when Smiley died during the Punk Hazard arc.
Marshall D. Teach isn't a good counter-example as he probably didn't use the conventional way to obtain his second devil fruit power. He must have used his powers to obtain the power instead of just eating it. I believe that he used his powers to trap the spirit before it could be reborn. I believe he absorbed the devil, the moment it got out of Whitebeard's body and before it could travel to the nearest fruit in order to be reborn.
The fact that Caeser deliberately put a sack of apples near the location he would kill Salamander indicates that he was aware of the fact that it would re-spawn immediately. If it wouldn't, there wouldn't be any point in putting a bunch of apples in the sleigh near Smiley. And even if it was just a major coincidence that the apples were there, it still shows that the Salamander fruit demon was reborn the instant Smiley died.
I don't think it is a well known fact though. Otherwise the Marines would have put a fruit similar to the fire fruit nearby Marineford to keep that awesome power within the Marines. Or maybe they did and Doflamingo stole the fruit in the end. We can only speculate on how Doflamingo got the Fire fruit, as it hasn't been revealed and I doubt it will be revealed further down the series.