Cfrgtkky

Permanent ice caps have not been a constant during Earth history. For example we know that in the past the poles were free from ice.

Therefore the oldest possible frozen sample is as old as the oldest permanent ice caps or frozen terrain on Earth. Anything that got frozen before that time has been thawed in the meantime.

The oldest frozen specimens would likely be roughly 15-30 million years old and would be whatever critters were on Antarctica during the Oligocene or early Miocene.

Around that time, Antarctica finished its split from other land masses with the opening of the Drake Passage between it and South America, allowing the Antarctic Circumpolar Current to begin keeping warmer waters away and permanently freezing the continent into what we know today.

Until it fully froze, conifer forests and steppes covered the continent, and if Antarctic fauna were anything like the rest of the world it was dominated by a mix of critters that were vaguely similar to today's large mammals, rodents, and sea life.

So, it looks like your frozen Oligocene Park will probably be decorated with odd-looking pine trees, and be filled with horses and mice with weird snouts. Not as awe-inspiring as a T-Rex, but still pretty cool.

As for finding frozen Neanderthals, it's possible but unlikely. In order to be found frozen, they would have needed to die in an area of permafrost that has been unchanged for the last 40-50,000 years, and their known range doesn't have many options for that. However, we did find a 5,000 year old mummy frozen in the Alps, so anything's possible.

a study published this week (October 10 [2012]) in the Proceedings of the Royal Society B estimates that DNA from bone has a half-life of 521 years

(Link)

That's the rate the DNA molecules spontaneously fall apart. This study does not address DNA in tissue other than bone, or how freezing temperature affects the deterioration of DNA, but I think it's still a decent estimate to start from.

How good is your technology at reconstructing DNA from teeny fragments in trillions of cells? Neaderthals went extinct 35,000 years ago. After that long (~67 half life periods) only 1/147573950000000000000th of the DNA will be left. The article sets 1.5 million years as the point after which DNA strands are too short to be read, but the point at which you can no longer recreate the whole genome might be much shorter than that.

If your technology were impossibly perfectly accurate, you might be able to approach the 1.5 million year limit.

With a well preserved bone less than a million years old, you can do anything you want.

Samples from a horse leg bone more than 700,000 years old have yielded the oldest full genome known to date.

The six-inch (15-centimeter) horse leg bone the team analyzed originated in the Yukon Territory of western Canada. Permafrost kept the remains in a kind of cold storage for about 735,000 years until scientists dug it out in 2003.

– World's Oldest Genome Sequenced From 700,000-Year-Old Horse DNA, National Geographic

We have the actual example of the Ice Man -- beaker culture neolithic discovered in the Alps. He was about 9000 years old.

So that can set some parameters:

Hunter or band traveling across and icefield that is in a pocket between multiple peaks. Dies in late fall. Exceptional snowfall period, so is buried under permanent snow cover which as the ice builds up puts him deeper.

Because it's a basin, the ice there doesn't move. When the ice builds up in thickness, there is a shear plane above it. Can't have glaciers feeding into the bowl either. So take a bowl that is surrounded by steep peaks that can avalanche into the bowl, but not form glaciers. Eventually the ice gets thick enough that it is above the bowl, and the excess flows off.

I think the Columbia Icefield on the border between Alberta and BC fits these criteria.

To me this would be a plausible event going back to the start of the last ice age. This would get you back to somewhere between 115,000 and 22,000 years ago.
Last Glacial Period -- Wikipedia For the longer period, you need to have some glaciation through the short inter-glacials. A mountain based shield would meet this requirement.

If you want a story line, "My father's father said that he knew a hunter who had crossed The Pass of the Winds." But in the hundred years since the cooling climate has created a permanent snowfield there.

Much of Antarctica is under water. Strip off the ice, and you have substantial inland seas. Antarctica without ice You could have various things trapped by glaciers closing off the openings. I don't know to what extent these levels freeze down. If there were hollows above the then present sea level you could trap land animals as described above. This could plausibly take you back to the beginning of the Antarctic ice cap something like 40 Megayear ago. I suspect that the timing of that is vague, so you might plausibly extend it back some. Dig into Antarctic paleo climate.

It is an extreme long shot but it might be possible, some day. Not really frozen however. The extreme desiccating effects of amber has been shown to preserve DNA, even in specimens of the right time period. And at least one fragment of a dinosaur flesh has been found preserved in amber. Several feathers are also known to exist.

The problems are three fold, not every piece of amber preserves DNA in fact most do not, and dinosaur material in amber are extremely rare, even by normal amber preservation standards. Lastly the DNA is extremely fragmentary so you are talking about massive reconstruction, to the point that said organism would be more invented than restored. It would also be the single largest and most complex genomic reconstruction in history, to the point you really would need a much better understanding of genomics and biochemistry than we have now. The only thing you have working for you is phylogenetic bracketing, and the fact said dinosaurs would be closely related to the ancestors of birds. In fact they would likely get more from reverse engineering proteins in the preserved specimen which survive much better, than the DNA, but that is an even more advanced technique.

The oldest known/recovered ice core so far is 2.7 million years old. It was pulled from Antarctica's Allan Hills area in 2015, which was coastal at the time the ice formed. Unfortunately the only animal specimens you'd be likely to recover from this site from this time would be marine lifeforms not too different from today's, as the continent had been cut off from South America for ~20-40 million years with the opening of the Drake Passage, which plunged the continent into the icy cold in the late-Miocene.

An even more extreme possibility (very unlikely, something like winning the lottery 3000-4000 times in a row).

Per this article, it is possible that ejecta after an impact from an asteroid could reach the space (even falling onto other planets). So, in case of a huge impact, a a rock sent into the space could countain some specimen (even a piece of a dinosaur, not necessarily a complete one).

In the space, it should not decompose, so it could remain preserved, inside an asteroid in orbit around the Earth or somewhere in the outer space, until our days, where it could be retrieved by a space probe.

Of course there are many issues to address (if you plan to write a novel, you would need some handwavium for them).

In the impact it is likely that the organic matter would be carbonized by the heat.

Such a specimen could be found only by chance, there is no way to detect it.

Moreover (and most important), in the space there would be no decomposition, but cosmic rays would rapidly degrade the DNA of the specimen; even if it could find itself inside the rock, probably this couldn't provide enough shielding to allow the DNA to survive up to 65 milions of years.