Go with the second explanation.

Imagine a rocket stage strapped down on a test stand. All the kinetic energy is going into the exhaust. From the observer's point of view, the rocket stage has zero velocity and the exhaust plume has much. The complete opposite is where the rocket is flying free in space at a tremendous velocity past a fixed observer. If the rocket is traveling at exactly the exhaust velocity as it passes the observer, the rocket will be reckoned to have all the kinetic energy since it's the only thing that has velocity relative to the observer. The exhaust that was emitted just as the rocket passed the observer would remain in the general vicinity of that observer, since the velocities cancel. It's like driving your car at 80 km/h and throwing a ball out of it backwards at 80 km/h (relative to the car). The ball would just drop to the pavement in that place. The magic of the Oberth Effect comes from correctly defining the observer's velocity state and leaving it alone.

If algebraic math is more your thing, imagine that kinetic energy is proportional to the square of the velocity. A given kilogram of fuel will give you a specific change in velocity. Forget for a moment that a rocket is a variable-mass vehicle. Just imagine two cases where 1 kg of fuel is expended from a given starting mass, the rocket being 1 kg less massive at the end of the burn. If the burn starts at, say, 10 m/s and ends at 12 m/s, the delta-v is 2 m/s. The mistake here would be to compute the change in kinetic energy as the square of the delta-v. You reckon it instead from the squares of the starting and ending values (accounting, of course, for the drop in mass, which we'll slightly ignore for the moment). So the change in kinetic energy is 144 - 100, or 44 units.

Now perform the same experiment starting at 20 m/s and ending at 22 m/s. The delta-v is the same, because we have the same mass rocket and burn the same mass of fuel as before. But the change in kinetic energy here is 484 - 400 = 84 units, almost twice as much of an increase as from the slower starting speed. This is because, as you know, a parabola -- the graph of a polynomial of order 2 -- gets steeper the farther away from the origin you get. So identical deltas along the x-axis result in greater changes in the y-direction the farther away from the origin they get.

If you're wondering where this extra energy comes from, just do the same calculation on the exhaust. If your exhaust velocity is 100 m/s, then the exhaust velocity *relative to the observer* in the first example is 100-10 m/s, or 90 m/s. In the second example it's 100-20 m/s, or 80 m/s. Relative to the observer, the exhaust has less kinetic energy in the second run. And relative to the observer, the rocket has more. And that's because of how the velocity reference frames are defined. You have to make the leap of regarding the exhaust velocity not as relative to the rocket, which is how it's canonically specified, but as relative to a fixed observer.