Both facts are certainly important in a real rocket, but I think that the thing which causes the confusion of the OP is mostly forgetting the KE of the exhaust rather than the fuel-as-payload effect. You can contrive scenarios to neglect the fuel-as-payload effect, but the KE of the exhaust effect is always there if you look at different frames.
Hmmm. Just looking at it from a simple W=FD perspective, it seems pretty obvious that it takes more work to accelerate to higher velocities since you're applying a force over a larger distance than before. However, I have no idea how to include the fuel exhaust into this.