Shoku, you remind me of someone from BBC. I really dig your style.
About reproduction: yes, sexual is faster and more adaptive, but it's aimed at the survival of the species and individuals, not at evolution. And it's not like in the brainspace time is a problem. Just a thought.
About oxygen: how about liquid ammonia-based life? Xenobiologists speculate a lot on different solvents and structural components. I don't think we should be so pessimistic.
And. I don't know how relevant it is (probably not relevant for quite a while), but I've come up with an idea for a statistics-based imaginary struggle for survival. Basically, we create an organism (evolve an organism from something before it), and turn its properties into sort of functions, well defined and sort of mathematical. For example, birdotherix - can fly, burns X kcal per hour, speed Y m/sec, take-off speed Z m/sec. So we take it by its functions, then we take a pool of survival situations, and randomly choose a defined number of situations against which to test birdotherix's functions, for example - a predator attack, a draught season, a forest fire. And "see" how well it fares. Although, there is a good chance it won't fare well against the forest fire. Well, what can you do? Survival of the fittest! And a sprinkle of random.
Just an idea.
About Jopax's bacterium: How do reproduction and a mineral shell work together for a unicellular organism? Does it have shed it before reproducing, by any chance? Or dissolve... And imagine, at some later time it evolves into a monster that dissolves bones of its victims.