Computational complexity and parallelism are orthogonal. Many EXP algorithms are embarrassingly parallel. You still have to do 2^n calculations, but if you have 1000 processors then it will take 1000 times less wall clock time because you're doing 1000 calculations at once.
The reason parallelism doesn't "solve" EXP problems is that parallelism grows linearly against something whose time complexity grows exponentially. It's not that it doesn't work at all, it's that if you want to solve the problem for 2n in the same time as for n, you need to double the number of processors. So the number of processors you need to solve the problem in whatever you define as a reasonable amount of time grows exponentially with n, but having e.g. 2^n processors when n is 1000 is Not Gonna Happen.
Having 1000 processors will still solve the problem twice as fast as 500, but that's not much help in practice when it's the difference between 50 billion billion years and 100.
The reason parallelism doesn't "solve" EXP problems is that parallelism grows linearly against something whose time complexity grows exponentially. It's not that it doesn't work at all, it's that if you want to solve the problem for 2n in the same time as for n, you need to double the number of processors. So the number of processors you need to solve the problem in whatever you define as a reasonable amount of time grows exponentially with n, but having e.g. 2^n processors when n is 1000 is Not Gonna Happen.
Having 1000 processors will still solve the problem twice as fast as 500, but that's not much help in practice when it's the difference between 50 billion billion years and 100.