Ouch I did some research and found
"Mammals, for instance, have an average species "lifespan" from origination to extinction of about 1 million years, although some species persist for as long as 10 million years."
Evolution: Library: The Current Mass Extinction - PBS
www.pbs.org/wgbh/evolution/library/03/2/l_032_04.html
So yeah, it would be a shame if space aliens visited and encoded a message to us in saber toothed tigers or trilobites.
Also I have no religious hangups, I'm a direct descendant of the ancestor of amoebas or whatever exactly, and if the message were encoded into whatever makes an amoeba an amoeba, well, its definitely gone now.
I think it would be hard to "infect" a species with stored data. They'd have to burn more protein to replicate that extra DNA material, which would provide a competitive advantage to any individual not carrying the data, so its not going to last long. Even thinking outside the box with a virus, wouldn't smaller ones have better odds of survival?