I think the main advantage of using a province system is that it makes sophisticated AI programming tractable. It does so by limiting the number of factors, such as the relative positions of forces, the AI needs to consider enabling it to make more intelligent decisions.
Chess programs are so good precisely because of this: the limit of 64 "provinces" on a chess board and strict movement rules and win conditions make alpha-beta AI algorithms work well partnered with exhaustive possible move tree searches and position scoring systems.
HoI cannot match that because you have many more "provinces", many more "pieces" that can in principle move anywhere, and many more "opponents" each with different objectives. It's a scale issue. But it does a pretty good job considering.
But take away the province-based system for a free-for-all and the AI would be much less able to identify realistic objectives, calculate reasonable plans of execution and make reasonably accurate tactical moves, certainly within an acceptable time frame. You need the core province object to hang the algorithms off.
As computing power increases you can increase the number of provinces, i.e. make the game more fine grained, which is exactly what has happened between HoI2 and HoI3. In principle, with enough computing power, you could put a global hex grid underneath the province/region/nation system which would in theory enable tactical battles in the style of say Operational Art of War (and make the game play a bit more like the Total War series, but retaining HoI's superior AI). I don't think current PC's have anything like the power necessary for this in a game on the scale of HoI3.
With sufficient computing power and further developments in the orders/AI assistance system started in HoI3 it concievable that this idea would work gameplay-wise, but there is a fundamental problem. Good tactical/operational level hex based war games like Operational Art of War are unable to beat human players of any sort of skill with equal forces, and this is dispite the fact that on any given map/scenario the designer can script certain AI moves based on overall battle plan and conditions occuring to give the human a run for their money at least.
In HoI the whole point of the game is that (more or less) anything can happen so no tactical scripting like this can be done in advance, so an average human player would run rings round the AI in tactical battle. The system HoI actually adopts, base on limited front size and province boudaries, makes the AI, all things being equal, a better tactician than most humans because it can accurately calculate the optimum attack sequences etc better than a human can (because the limited number of variables make this tractable). That means in order to beat the AI you have to know what you are doing strategy-wise or you will get trounced - i.e. HoI is a challenging game (which is why we love it).
Take away the province system, stacking limitations etc that give the AI this tactical edge at the front and the game will become easier in that you would be able to beat superior forces through tactical nouce and trickery the AI is unable to match. Basically a bit like Total War games.