Top quality propulsion can shrink the time to 50 million years, which means somebody can colonize the galaxy faster than dinosaurs can evolve into talking monkeys.
So there has been plenty of time for robotic probes to colonize the galaxy. So where are they?
In fact, using current technology, we actually could build a "self-replicating probe" loaded with algae and other photosynthetic single-celled organisms. So we really can't rule out ourselves as the evidence we're looking for. We might even be evidence that such probes usually malfunction.
I like that.
AFAIK, mammals existed during the dinosaur era. But they occupied a tiny ecological niche and were physically tiny. They survived the asteroid hit because they were tiny.
The absence of dinos enabled them to eventually occupy niches occupied by dinos.
They're bacteria and they already colonized Earth.
http://en.wikipedia.org/wiki/Panspermia
My hunch is that it's true: that when we get better at detecting it, we'll discover bacteria/viruses/spores of various kinds all over the place (including Mars and other solar system locales).