It just means that the dark lord is damned fast about replacing his second. Which makes sense because in the next movie he is supposed to do it again - successfully. (And note that he is already training the possible replacement.)

As for size of militaries, my judgement is based on comparing one system to Earth. We have multiple countries with militaries in the ballpark of a million or more. Many more don't, but could raise such in the event of a protracted war. Even if we assume that this universe is less populated, at 10,000 soldiers or equivalent (eg drones) per planet (which is on par with a medium-sized force of peacekeepers that the UN manages to organize fairly routinely), we would still be talking an army of hundreds of millions.

Putting it into some perspective, more past and present military people will see Lucas' film than will be in this galaxy-shaking Grand Army!

Cheers,
Ben