While it's true "the role of sex is not completely understood" in evolution, most current research points to co-evolving parasites as a major force that makes sex a good evolutionary move. It increases inter-generational variation while at the same time preserving viability (because both parent organisms are viable) which merely adding randomness would not do. Parasites are typically incredibly specialized because the hosts always evolve pretty good first-line defenses, so the additional genetic variability that sex produces from generation to generation becomes a considerable added benefit to the host, because the parasite population is always playing catch-up. Like many things in evolution, the war is never won, but sex tips the strategic balance in favour of the host.

That said, this kind of formal, mathematical approach to evolution is becoming increasingly powerful, and it's worth speculating if there might not be a provable theorem connecting random DNA variation and the laws of probability at the molecular level with the fact of macroscopic evolutionary change, speciation, etc... something like Boltzmann's H-theorem in thermodynamics, which attempts to show how micro-physics (kinetic theory) can be used to prove the macroscopic 2nd Law of Thermodynamics.

This would make evolution not a theory but a theorem, which I call "Darwin's Theorem". I've played around with the math a bit (I'm a physicist, not a mathematician) without getting anywhere, and wrote a what-if novel about the possibility (it plays with even more speculative ideas as well), in part with the thought of popularizing the idea, because I think it's worth people thinking about: http://www.amazon.com/Darwins-Theorem-TJ-Radcliffe-ebook/dp/...