It's not unlikely that all the solar system's planets have been contaminating each other for billions of years. All it takes is a big asteroid impact and some luck, and then some bacteria hitches a ride.
The tough part is of course thriving after the organism arrives. Given Mars' current climate and surface perchlorate levels, I'm not convinced it's likely that something from here takes root over there without some help.
The whole chain of "really big rock -> chunk of Earth leaving the gravity well -> getting into some kind of stable orbit where it can be pulled into Mars -> surviving re-entry on Mars" doesn't seem like it would happen enough times to create the kind of odds of success that would be needed for a bacterium to successfully colonise Mars.
Yes; but those temperatures may not penetrate deep into the body of the rock; so there still might be biology surviving.
The bit that sold me on the idea was when they noted that the complexity of life seems to double every 250m years. But apparently if you roll with that assumption and extrapolate all the way back to the simplest conceivable organism, you end up at time when earth didn't exist and the universe was young.