Turn based could very well work for Paradox- IF THEY REDUCE THE AMOUNT OF PLAYERS.
I'm going to use War in the West/East by Gary Grigsby as an example.
Both have a 7days/turn system, and are infinitely more complex than Hearts of Iron 3. These games are able to be due to the turn based system allowing more system usage for decisions than an RTS. They manage this by reducing the players to Axis and Allies only. This kind of system would not work in Europa Universalis or Crusader Kings due to the 4 billion states, but smaller games would work.
They could also try to do it in something like Victoria, but that would mean dumbing down the smaller nations to non-players. You wouldn't be able to play as Hannover or Hessen for example, and their actions would be reduced to just simple things in order to reduce turn times. The trade off is essentially depth for size. I think the majority of players would be fine with that because most don't do a German unification with Luxembourg, but it would just depend on Paradox's mindset.
While I'm a big fan of War in the East (haven't gotten around to WitW, but expect I'll enjoy that too), a couple of points:
- I wouldn't argue, for a second, that WitE is "infinitely" more complex than HoI3. Its production model is hands-off and railroaded, it's political model non-existent, its naval side of things equally non-existent. Yes, it tracks equipment and manpower at a far more granular level, and tracks combat at a more granular level, but from a gameplay perspective this just feeds into combat results. HoI3's supply system is definitely far more complex (and, I'd argue, far better at simulating logistical difficulties over longer distances). Both games are quite complex, with different focusses, but on an overall gameplay level, I'd rate HoI3 as more complex than WitE (but WitE as a more difficult game, as it's AI is more challenging than HoI3s, although it still has some issues).
- My average turn time on a clear turn in WitE when I'm on the offensive is around 65 minutes. However, when I'm on the defensive it's closer to 30-40 minutes. No problem in single-player, but in MP that's a lot of time sitting around for whoever's on the wrong end of the offensive.
- Most of the system usage in WitE is for tactical decision making, with a bit less for operational, made more complex by the size of the theatre in question. There's no reason this couldn't be applied to multiple nations (although it would, of course, result in slower running when there's warfare going on larger and more complex than Barbarossa).
On topic, I'm sure I'd enjoy a turn-based PDS game, and if they wanted to do one would give it a go, but plenty of people already to turn-based strat titles, and very few indeed make anything like PDS does, so if they're happy doing what they do, I'd personally prefer they keep doing what they're doing