If a person were to die on the Moon or Mars, would the body decompose?
There wouldn't be enough oxygen for any bacteria to decompose the body, right? Not to mention, the radiation of space might kill off most organisms on it. So would it decompose, given millions of years?
You should read "The Gentle Giants of Ganymede." The beginning starts with present-day astronauts discovering a (something like) 100,000 year old human skeleton on the moon. Sorry...not an answer, but your question so much reminded me of that novel.
In these conditions, bodies mummify.
The microbes that live in you, wouldn't survive the freezing, dessication and radiation. There is no real upper limit on how long a mummified body could exist in space. There would be nothing to cause the body to change, and so it would remain. There would be a slow breaking down of surface proteins, due to UV light, and eventually micrometeorites would erode the body, but these processes would take many millions of years.