Things that aren't yet fossilized are usually referred to as "subfossils" , which is probably how you want to search for this information

Anyway, I did some research and here's some things I found

This paper describes camel bones from about 3 million years ago on Ellesmere Island. They are embedded in layers of leaf and moss that are described as "subfossil" and the bones themselves were fresh enough to allow the removal of significant collagen for analysis. There have been reports of even older collagen/soft tissue, but that's in bones that have clearly been fossilized. I'm guessing these bones are closer to what you are talking about, given the context of their preservation.

Here's a similar study from the same area looking at beaver teeth and local vegetation, comparing isotope ratios to see what beavers were eating. So we are talking about plant and animal remains that still have organic material that isn't too heavily modified.

Finally, here's a paper that managed to snag DNA from mammoth teeth slightly more than a million years old. That's less than the previous studies, but DNA is more fragile than collagen, so we are talking better preserved specimens here.

Anyway, the answer is probably "A few million years, and you find them in frozen sediments"

Although who knows what might be frozen under the ice at the bottom of Antarctica