Something I liked about AI War was that its core mechanics (combat model, per ship mechanics, and per-ship AI) was deterministic, or at least, did not explicitly include any sorts of randomness. It helped avoid the desire to "save scum" in order to game the RNG, and it made it easy (well, easier) to reason about how units interact.
Now, things I don't mind randomness coming into is "macro" level things. Map generation, AI players' macro-decisions (where to retreat to, where to attack) I don't mind randomness. For things like map generation, that is "one time randomness", that doesn't deny information to the player (long term at least). Similarly, some randomness in the AI players' decisions helps to keep the feeling that you are playing against someone else (the future actions of other "player agents" is one of the few places where "obscuring information" to the player is a good thing to have in game design).
Now, this isn't a "deal breaker" for me. If there is a "core mechanic" deficiency that can be solved elegantly through some randomness, and no one can come up with deterministic alternatives that don't have worse shortfalls, then I can understand that.
An example of this is the "50% chance miss of low ground to high ground" mechanic of SC1/BW.
In SC2, there is a real issue where having high ground does not confer enough advantage, which leads to (among other things) compromised defenders advantage and "snowball" situations being too easy to trigger.
Lots of the members of the community have though hard about some way to fix that for SC2, but so far from what I have seen no one can seem to come up with a better way than the randomized advantage of the SC1/BW. So, I could live with that if it came back (not that Blizzard has even tried to address this yet, but still).
Also, on a note about randomness, I appreciate the dedication to true randomness. Sure, there are tweaks in the algorithm that uses the random numbers that avoid "worst case" scenarios (the "brutal picks" system of AI HWs, etc), but there has been no compromise to the randomness of the RNG itself. I like that, and for where randomness will be used in AIWII, I would personally like to see that kept.