I would argue that there is a place for the complexity of a reduction to matter, but that we do not use it in determining whether there is a reduction.
Let's take a concrete example: we consider Newtonian dynamics to be reduced to the Schroedinger equation, and we can convince ourselves of this deduction with some efficiency. But the efficiency is the efficiency of verifying coverage of the behavior, not of actually doing the reduced field in terms of the more basic one.
But that means this is, intrinsically a verification, i.e. an "NX" problem, and P vs NP is not part of the way we should look at this complexity. We do not need to solve the old domain in the new one, only to believe the math that proves coverage. We also generally don't measure the complexity of a proof in orders of magnitude. We expect such proofs to be finite. (So that makes question 3 silly.)
So even though the reduction does not give us a tractable way of computing the higher-order behavior from the lower-order behavior, we consider the problem reduced. But we do consider these two scopes to be different domains of physics. We do not attempt to take Newtonian measurements in quantum terms. (The same it true of thermodynamics, we do not measure temperature in terms of average speeds of particles, we use distributions and move away from actual kinetics as a basic approach. And of astrophysics, where we realize we need to attend to relativity.) I would argue that this is the point at which complexity matters.
We consider the opposite reduction impossible. Because we can do something like the deBroglie or Bohm reduction, which breaks things up in terms of moving waves shaped by standing ones, or particles directed by waves, and so uses Newtonian terms. But we find an infinite regress trying to pin down "the phase of the particle's wave", or "the location of the particle being guided". The to zoom in produces more and more unknown Newtonian velocities, which we cannot compute without global information. We can't be sure those values actually exist, so we generally don't consider this a reduction.
Again, the complexity is irrelevant to whether or not there is a reduction. It does not matter whether or not the deterministic under-model would be staggeringly complex, only that it is in principle circular.
This latter case gives a good example of your question 2, and the answer is that it depends who you ask. Different people look at this in either of the ways you suggest.
If a simulation is not good enough, we can back away from the complexity by simply not considering things reduced, and imagine a basic lack of similarity between the systems. If a simulation is good enough, we can say the values theoretically exist, but are 'hidden', and their values can never be known, but we can choose values in our simulation, and it works. (We even know how close we can get to knowing them, in principle, if they do exist, and why.)
So we can claim that there is a deterministic model, though not a reduction to it, or that there is none at all.