Insects, algae, lichens, bacteria etc. are might be stronger contenders than inorganic self-replicating machinery. They're pretty good at surviving harsh environments already, evolve pretty quickly, and often have life cycles adapted to multiple types of environment and timescales of activity, much like multi-stage spacecraft.