I think you've misread the article. It says rocket engines can attain up to 70% $\eta_c$, which is only the cycle efficiency (how well it turns the energy of the fuel into mechanical energy). This is not the propulsive efficiency.
Unfortunately, for a rocket much of this mechanical energy is used to (wasted..) increase the KE of the exhaust rather than the rocket. As the article mentions, optimum efficiency is when the exhaust speed and rocket speed are matched. But this ends up being horrible for fuel consumption.
Being able to throw the mass of the earth or the atmosphere around makes regular propulsion much more efficient.
In one of your comments you linked to the question Velocity and kinetic energy, violating galilean relativity and said that the efficiency of a car drops with speed. I wouldn't agree with that statement. The question was specifically about interpreting energy in different frames.
If we stick to to just the frame where the ground is at rest (a very valid frame for travel on the earth), then the theoretical efficiency of your battery car approaches 1 as you eliminate drag. The energy of the battery can be given into KE of the vehicle almost entirely since the earth is so massive.
Do cars legitimately use 100X as much fuel to go 100km/h => 101km/h as
0km/h => 1km/h?
In the frame of the ground, yes (although it's more like 200x).
It's because cars are pushing on the ground. When the ground is going backward at 100km/h, it's much, much harder to push forward along it. You probably need additional gearing to make the wheels go faster compared to your power source. But when you do that, the force on the power plant goes up.
And do rockets not have this problem?
(Useful) rockets don't start off moving at high speed. They start off moving at slow speed. When at slow speed the fuel burn "pays" for accelerating both the rocket and the remaining fuel.
Later, the rocket can use the accelerated fuel (which now has much more energy than it did on the ground) to accelerate even faster.
The rocket is using not only the chemical energy content of the fuel, it is also using the KE of the fuel. We ignore that in the car. It's like the first part of the burn is also charging the fuel. We get to burn that charged fuel at the end, so it works better.
So is it true that, at high speeds, fundamentally a car is staggeringly less fuel-efficient than a rocket?
Yes. If the only way you can accelerate is by pushing backward on the ground, and the ground is receding from you at 1km/s, you're going to have a very tough time accelerating. There are no cars that can do it, even if there were zero rolling/air resistance.