When i say randomness i dont necessarily mean sandbox. I mean plausible. Its a bit ridiculous say as the Soviets, i can delete my entire military, because i know exactly when and where the Axis will attack, i know pretty much exactly how much time i have to rebuild, and i know that no other nation will ever jump across my empty borders.
Replaying exactly how the war took place as many people here do, i just dont see it. Its still not historical, there are way too many elements missing or misrepresented, so any illusion that "i beat the Soviets when Hitler couldnt" is purely that, an illusion. In fact i cant remember any other game where i knew in so much detail everything that was going to happen before hand. Thats why you see so many players after awhile playing such off beat scenarios, like trying to take over the world as a minor.
If you play mostly MP as it seems you do then you dont necessarily have to deal with it as much as the human element is the biggest randomizer going. Sooner or later youll play opponents that will simply do things you dont expect, and youll be challenged and forced to react, and it will be a test of your skills.
There are many players whom want a total sandbox, im not one of them but i have often said it seems most players play Norm or VH, so maybe the game would be better suited with historical/plausible/sandbox modes instead.