WarCraft III had a good amount of randomness -- %-based critical strikes, evasion, damage ranges, movement speed ranges, dodgeable projectiles. Also RPG style heroes for each faction which could heavily influence the tide of a battle when used well. Combat is of course not as involved as Overgrowth seems, since it's still an RTS. That sounds like it fits your proposal, but I'm not sure?
