It is a bit more complicated. You should be able to land without the use of energy but you have to pass your momentum to something - and this passing on of momentum will be the same in both cases. Let us consider a "spherically-symmetric-chicken-in-a-vacuum" model to see this explicitly.
Momentum conservation and propelled mass
The spacecraft of mass $M$ is hovering just a bit above the surface of the planet at zero vertical velocity (it is hovering above the surface to be able to propel fuel downwards). Suddenly, it propels a single pulse of fuel with velocity $v_{\rm f}$, mass $m$ and total momentum $p_{\rm f} = m v_{\rm f}$ downwards. Due to momentum conservation, the spacecraft will start to move upwards with a momentum with equal magnitude. If the pulse is just enough for the spacecraft to escape the planet with velocity $v_{\rm e}$ it must hold that $$p_{\rm f} = m v_{\rm f} = M v_{\rm e}\,,$$ or that the velocity of propulsion of the fuel must be $$v_{\rm f} = \frac{M}{m} v_{\rm e}\,.$$
But your assumptions are that $M \gg m$ which in combination with the previous formula leads to $v_{\rm f} \gg v_{\rm e}$. Even though the model is vastly simplified, the basic conclusions are valid. In more complicated models you will continuously loose mass so that the propulsion will have varying effects but the "before vs. after" equation will look the same on average because momentum conservation always rules.
The very same relation would be valid for a descent. Say you have fallen from rest at infinity up to the surface of the planet and due to energy conservation now have a velocity equal to $v_e$ - but downwards. Momentum conservation! You have to throw the momentum away not to get smashed into pieces, so you propel all your momentum into a single fuel pulse downwards. The momentum of this pulse must be again equal to $p_{\rm f}$ so all the previous relations hold.
Energy balance
It is true you have to propel the same amount of mass at the same speed in both cases, but it is also interesting to see what happens to energy. In the takeoff you have before the pulse
$E_0=0$
and after the process a lot more kinetic energy due to the motion $$E_{1} = \frac{p_{\rm f}^2}{2m} + \frac{p_{\rm f}^2}{2M}$$ I.e., the smaller the $m$, the more energy you use in the takeoff. However, in the descent you have before the pulse $$E_0 = \frac{p_{\rm f}^2}{2M}$$ and after the pulse $$E_{1} = \frac{p_{\rm f}^2}{2m}$$ so in principle, it should be possible to save a lot of energy just by an elastic "passing-on" of the momentum. This is actually something we know very well from practice where we have the atmosphere to give the momentum to via a parachute or such.
From this "fuel-pulse" mode you can see that if you are able to pass your momentum to a mass of about your magnitude, in principle you should be able to land without burning a drop of fuel (I.e. without exerting any stored chemical/electric/nuclear energy).
The fact is that even if you just want to use mass and energy stored in your spacecraft, you will not be accelerating it all from zero but from the escape velocity $v_{\rm e}$ to $v_{\rm f}$. You can thus use your fuel to push and propel some dead carriage because your engines will actually propel at their original speed plus $v_{\rm e}$ in the planet rest frame.
CONCLUSION: You have to propel roughly the same mass at roughly the same speed both during take-off and landing, but you do not have to burn so much fuel during landing.
Just a note on the assumption of no mass change for a reaction engine. For a Moon to Earth escape we have $v_{\rm e}\approx 11 000\,\rm m/s$ which is way above the possibilities of a classical bipropellant rocket with maximum $v_f \approx 5000 \, \rm m/s$. Even if you used some of the state of the art ion thrusters, you would not reach more than a few times more than $v_e$. But that is in conflict with the conclusion $v_{\rm f} \gg v_{\rm e}$ from the momentum conservation balance and the assumption $M \gg m$. So the assumption of a small propelled mass $m$ in comparison with the mass of the spacecraft $M$ is not realistic.
You've noted that at high velocities, a tiny change in velocity can cause a huge change in kinetic energy. And that means that the thrust due to burning fuel seems to be able to contribute an arbitrarily high amount of energy, possibly exceeding the chemical energy of the fuel itself.
The resolution is that all of this logic applies to the fuel too! When the fuel is exhausted, it loses much of its speed, so the kinetic energy of the fuel decreases a lot. The extra kinetic energy of the rocket comes from this extra contribution, which can be arbitrarily large.
Of course, the kinetic energy of the fuel didn't come from nowhere. If you don't use gravity wells, that energy came from the fuel you burned previously, which was used to speed up both the rocket and all the fuel inside it. So everything works out -- you don't get anything for free.
For those that want more detail, this is called the Oberth effect, and we can do a quick calculation to confirm it. Suppose the fuel is ejected from the rocket with relative velocity $u$, a mass $m$ of fuel is ejected, and the rest of the rocket has mass $M$. By conservation of momentum, the velocity of the rocket will increase by $(m/M) u$.
Now suppose the rocket initially has velocity $v$. The change in kinetic energy of the fuel is
$$\Delta K_{\text{fuel}} = \frac12 m (v-u)^2 - \frac12 mv^2 = \frac12 mu^2 - muv.$$
The change in kinetic energy of the rocket is
$$\Delta K_{\text{rocket}} = \frac12 M \left(v + \frac{m}{M} u \right)^2 - \frac12 M v^2 = \frac12 \frac{m^2}{M} u^2 + muv.$$
The sum of these two must be the total chemical energy released, which shouldn't depend on $v$. And indeed, the extra $muv$ term in $\Delta K_{\text{rocket}}$ is exactly canceled by the $-muv$ term in $\Delta K_{\text{fuel}}$.
Sometimes this problem is posed with a car instead of a rocket. To understand this case, note that cars only move forward because of friction forces with the ground; all that a car engine does is rotate the wheels to produce this friction force. In other words, while rockets go forward by pushing rocket fuel backwards, cars go forward by pushing the Earth backwards.
In a frame where the Earth is initially stationary, the energy associated with giving the Earth a tiny speed is negligible, because the Earth is heavy and energy is quadratic in speed. Once you switch to a frame where the Earth is moving, slowing the Earth down by the same amount harvests a huge amount of energy, again because energy is quadratic in speed. That's where the extra energy of the car comes from. More precisely, the same calculation as above goes through, but we need to replace the word "fuel" with "Earth".
The takeaway is that kinetic energy differs between frames, changes in kinetic energy differ between frames, and even the direction of energy transfer differs between frames. It all still works out, but you must be careful to include all contributions to the energy.
Best Answer
Exactly the same problem can be observed in case of automobile moving on the surface of the Earth. Suppose, a car of mass $m$ is moving at speed $v$. Then it burns some fuel and increases its speed to $2v$. Then the change of kinetic energy is $$ \frac{m(2v)^2}2 - \frac{mv^2}2 = \frac32mv^2 $$ However, if you consider this situation from a point of view of another car, moving alongside the first one with the speed $v$, then the initial speed of the car is zero, and the final speed is just $v$, so the change of the kinetic energy is $$ \frac{mv^2}2 - 0 = \frac12mv^2 $$ Thus, from this point of view the burned fuel produces 3 times less energy increase. What is going on?
You have forgotten the kinetic energy of the Earth. The burned fuel gives its energy to the whole system, which is not an isolated car, but a system of the car and the Earth. If we treat this system as a closed one, then its momentum should be conserved. When the car accelerates from speed $v$ to speed $2v$ (or, in the second case, from speed 0 to speed $v$), its momentum increases by $mv$. This change of the car's momentum is compensated by the change of the momentum of the Earth. To compensate the forward momentum of the car $mv$ the Earth gets an additional backward speed $u$: $$ Mu = mv,\qquad u=\frac mMv, $$ where $M$ is the mass of the Earth.
So, in the first case the initial speed of the car was $v$, the initial speed of the Earth was 0. The final speed of the car is $2v$, the final speed of the Earth is $-u$. The change of the kinetic energy is $$ \frac{m(2v)^2}2 + \frac{Mu^2}2 - \left(\frac{mv^2}2 + 0\right) = \frac{3mv^2}2 + \frac{M\left(\frac{mM}v\right)^2}2=\frac{3mv^2}2+\frac{m^2v^2}{2M} $$ Since the mass of the Earth is much larger than the mass of the car, $M\gg m$, the second term is almost zero and we get our old answer, $\displaystyle\frac{3mv^2}2$.
However, in the second case the situation is quite different. The initial speed of the car is zero, but the initial speed of the Earth is $-v$. The final speed of the car is $v$, the final speed of the Earth is $-(v+u)$. Thus, the change of the kinetic energy is $$ \frac{mv^2}2 + \frac{M(v+u)^2}2 - \left(0 + \frac{Mv^2}2\right) = \frac{mv^2}2 + \frac{M(v^2+2vu+u^2)}2-\frac{Mv^2}2= \frac{mv^2}2 + \frac{M(2vu+u^2)}2 $$ Now we substitute $\displaystyle u=\frac mMv$ in the second term: $$ \frac{mv^2}2 + \frac{M(2v\frac mM v+\left(\frac mMv\right)^2)}2 = \frac{mv^2}2 + \frac{2mv^2}2+ \frac{m^2v^2}{2M} $$ This is exactly the same answer which we got in the first case. The last term is again vanishing in limit $M\gg m$, so the simple answer is again $\displaystyle\frac{3mv^2}2$.
Surprisingly, in the second case a substantial part of the energy of the burned fuel is used to increase the kinetic energy of the Earth, not the car. We consume two times more energy to accelerate the Earth than the car itself!
The same reasoning is valid for your original question. You have forgotten about the kinetic energy of the jet. In order to accelerate the rocket you burn some fuel, its energy is used to accelerate both the rocket and the jet. If you carefully calculate the change of the kinetic energy of the rocket and the jet in both reference frames, you'll find no discrepancies.