The La Brea Tar Pits in Los Angeles are the perfect answer to this question.
If you dig in the asphalt pits, you find bones of animals that lived 8,000 - 40,000 years ago. Since all that is left are bones, the soft parts must have decomposed. I don't know if the tar slows the rate of decomposition, but it doesn't stop it. Here is a good web site on the tar pits:


http://www.ucmp.berkeley.edu/quaternary/labrea.html