Indeed wowbagger.
I would define an outcome as "random" if identical starting conditions could lead to significantly different outcomes. I think this would mean that any cahotic physical system would be random by this description, as the infinite precision would mean that quantum fluctuations would eventually have a significant difference, in a way that isn't the case for non-chaotic systems. ETA: Sol, is that still the understanding? IIRC it was when I was an undergrad, but I tended to concentrate on solid-state physics...
I agree that there are situations where, despite the inherently random nature of the process, there are aspects that are highly predictable.
Talking about the process, mutation is essentially "undirected" with respect to the direction of evolution. It is needed as a source of variation, but the "clever" part is natural selection.
I have posted many times before why I think natural selection is a random process, in a similar way as a bent game of dice is random. Basically traits modulate the chances of reproducing, but for any individual trait, the odds are still stacked against it surviving the first generation. I don't just believe that there are chaotic systems involved that affect natural selection, e.g. the weather, but that these chaotic systems are also affetced by truly random quantum events.
Furthermore I would say that as organisms affect the selective environment for other organisms in their ecosystem, then there are complex feedback loops in place which depend on random events. To me this implies that if you were able to have universes with identical starting conditions, the course of evolution in each "Earth" would be different. Looking at the diversity in life just tens of millions of years after each large extinction event, and the differences between each one, I would say that not only was humanity just a lucky accident, which only seems special to us, but that it was only pretty recently when it became inevitable that our ecological niche would be filled (Neanderthals being an obvious alternative candidate tjhat could fill "our" niche).
If there is not any inevitibility about what would evolve, and indeed whether some of the less probable* niches are filled, then I would say that it is perfectly valid to talk about the results evolution as being "not-predetermined"**.
I think the random, yet somewhat predictable nature of natural selection is important as I have heard some people (not sure if they were sincere or creatinists) asking whether all animals that "survive" are "fitter" than all that don't. My answer is no, because it is like a loaded dice game, but over time the odds will out.
*Given the timescales, and the length of time that there have been large mammals, it could be argued that our niche (as a, "fire-using social animal") might have been potentially fillable for some time before it was.
**I do agree that describing evolution as "random" is misleading, due to the connotations, unless you try to explain what is meant by this. However, I also think that "nonrandom" is also misleading, and probably even more wrong, but then I am happy talking about random events being highly predictable in certain fashions...