The tissue wasn't soft until Dr. Schweitzer (well, a grad student, more likely) dissolved all the calcium-containing minerals in that chunk of fossil with EDTA. The remaining proteinaceous stuff had been encased in those minerals well enough that bacteria couldn't eat it, water couldn't hydrolyze it, and oxygen couldn't oxidize it.
That's my latest reasoning, and it is only a minute or so old. I think that puts it in the running for the latest, no?
Second-latest reasoning may be this, from Live Science in November 2013:
Iron is an element present in abundance in the body, particularly in the blood, where it is part of the protein that carries oxygen from the lungs to the tissues. Iron is also highly reactive with other molecules, so the body keeps it locked up tight, bound to molecules that prevent it from wreaking havoc on the tissues.
After death, though, iron is let free from its cage. It forms minuscule iron nanoparticles and also generates free radicals, which are highly reactive molecules thought to be involved in aging.
"The free radicals cause proteins and cell membranes to tie in knots," Schweitzer said. "They basically act like formaldehyde."
Formaldehyde, of course, preserves tissue. It works by linking up, or cross-linking, the amino acids that make up proteins, which makes those proteins more resistant to decay.
Schweitzer and her colleagues found that dinosaur soft tissue is closely associated with iron nanoparticles in both the T. rex and another soft-tissue specimen from Brachylophosaurus canadensis, a type of duck-billed dinosaur. They then tested the iron-as-preservative idea using modern ostrich blood vessels. They soaked one group of blood vessels in iron-rich liquid made of red blood cells and another group in water. The blood vessels left in water turned into a disgusting mess within days. The blood vessels soaked in red blood cells remain recognizable after sitting at room temperature for two years.
Edited by Coragyps, : addition of Live Science quote