The argument in the question is as follows:
- There is a finite probability of finding the particle inside of the barrier
- If the particle is inside the barrier its energy is negative
- States with negative (kinetic) energy are impossible
The seeming paradox here is due to mixing classical and quantum concepts. Let us first note that there is no state inside the barrier. The state of a particle in this case a scattered wave, extending to infinity. The probability of measurement finding a particle inside the barrier is indeed non-zero. On the other hand in classical physics the state is identified with a specific location and momentum, i.e. the measured position of the particle is its state. Once we localized a quantum particle at a specific location, it is no more in the scattering state, and has undetermined momentum and energy.
Secondly, let us consider what the conservation of energy means in quantum mechanics.
- We could view it as a fact that a particle in an energy eigenstate remains forever in this eigenstate. But this is not relevant here, since we perform a measurement, collapsing the wave function to a position eigenstate.
- It can be viewed from the point of view of the uncertainty relation, as discussed in the answer by KDN.
- Finally, it can be viewed from the point of view of the correspondence principle and the Ehrenfest theorem, where it will be conservation of the energy average in the quantum mechanical sense:
$$\langle\frac{p^2}{2m}\rangle + \langle U(x)\rangle \neq \frac{\langle p\rangle^2}{2m} + U(\langle x\rangle),$$
where on the left we have the average energy in QM sense, whereas on the right is its classical estimate implied by the argument in the question. These are not the same.
To summarize: quantum mechanics appear paradoxial only as long as one relies on the intuition, grounded in classical phsyics.