"I would expect the same amount of fuel to be converted into the same increase of velocity, regardless of the current speed."

Yes, unlike an automobile, a space rocket accelerates the same way for the same amount of fuel regardless how fast it is going. Also it would be practical to rate the conventional power of a rocket motor from its work rate on the rocket propellant when the rocket does not move (that rocket is fixed to a test stand of some sort).

"I would expect the same amount of fuel to be converted into the same increase of velocity, regardless of the current speed."

Of course you are right and also the formula that you have cited appears to be correct. Unlike an automobile, a space rocket accelerates the same way for the same amount of fuel regardless how fast it is going. Also it may have a velocity in the sense of whatever arbitrary reference frame you would like.

In that case it will pick up next to zero kinetic energy per unit jet energy at times when it has a velocity that is next to zero. At those times almost all of the engine work will be spent on accelerating the propellant. When the rocket is moving right up close to the exhaust velocity then the engine work adds next to nothing to the kinetic energy of the jet.

The formula does not work in the case where the rocket is slowing down in the reference frame.