Suppose a ParallelTable invocation parallelizes a module which in turn invokes ParallelTable. Is it possible that there will be a deadlock situation wherein the second ParallelTable invocation can't proceed because the first one has been allocated all the available CPUs?
No. The second one simply won't have any effect.
Just try, and see the warning messages.
You can read about how parallelization works here:
It is not CPUs that get allocated, but kernel processes (of which you may launch as many as you want). If a parallel command (such as
ParallelTable) is run on the main kernel, it distributes its computation to subkernels. If it is run on a subkernel, it reverts to the non-parallel equivalent (i.e.
Table), and prints the above warning message.