Why doesn't car fuel/energy consumption scale like the cube of the velocity?

There are two extra things to consider here.

First, in even the absolute simplest case, your car is not just fighting wind resistance (which indeed follows a $F \propto v^2$ law at these velocities) but also various static friction forces, usually following an $F \propto v^0$ law. And as you might imagine some of these forces are dropping based on what gear you're in, as some of the static friction is internal to the engine block. You can also read "constant force" as meaning "constant energy expenditure per unit of distance," which clarifies that something like the pistons compressing air but then that now-hot air being vented out (as it will be) turns out to be a constant force on average.

Now this force that's proportional to the square of velocity might also pick up a horizontal component coming from a cross-breeze of speed $u,$ which looks at first like it doesn't matter (Pythagorean theorem, $|[u,~v]|^2 = u^2 + v^2$) but actually does (because you also have to project it back onto the direction of motion of the car to calculate work, which involves multiplying by $v/\sqrt{u^2 + v^2}$.) So your actual force equation is probably much closer to $$F = F_0 + k v\sqrt{u^2 + v^2},$$ where $k, u$ are probably being approximately constant but potentially $F_0$ might be much lower at 200 km/hr versus 100 km/hr because you have probably shifted to a higher gear. (Realistically the next step in adding accuracy to this model might be writing $k = k_0 + \alpha~u/v$ or so to add the effect that when there is a cross-breeze it takes the drag force over a less-streamlined orientation with respect to the car.)

Second: you are trying to use power $\vec F \cdot \vec v$ to look at fuel consumption per unit distance, but a given amount of fuel probably gives a certain amount of energy and power is an energy expenditure per unit time. Therefore when you want to know fuel consumption per unit distance you need to multiply power by the time it takes per unit distance -- this is the inverse of the velocity. So actually fuel consumption goes like $\vec F \cdot \vec v /|\vec v|$ and your fuel consumption should only scale like: $$F_0 + k v \sqrt{u^2 + v^2}.$$

So in summary, one of these factors of 2 is flat-out wrong for calculating fuel efficiency, the power may go as speed cubed but the energy per unit distance only goes with speed squared in the limit $F_0 = 0,~u = 0.$ The other missing factor of 2 probably comes from the fact that in the lower gear the drag forces $F_0$ and $k v^2$ are approximately comparable, whereas in the higher gear you've reduced $F_0$ considerably by upshifting -- but some components of it probably also come from a slight cross-wind that both acts as a linear drag force and redirects the airflow over a less-aerodynamic profile over the car.

It does obey the laws of physics. It is a complicated system that it does not the drag force or the fuel consumption is not always proportional to $v^3$ for all values of $v$.

The general equation for drag is given by:

$$F_{drag} = C_1v + C_2v^2 + C_3v^3 + \ldots$$

The drag force depends on the constants $C_1, C_2, \ldots$ and $v$.

For very small velocities, the lower order terms are more significant compared to the higher order terms. For large velocities, the higher powers become more significant.

The amount of fuel you need is a function of not just of the drag force, but also of other external forces such as friction. The amount of fuel consumed has no decent relationship with the drag force acting. It depends on the time you travelled, how fast you accelerated, etc.

The work done by the drag force is given by:

$$W_{drag} = \int_a^b \vec{F}_{drag}.d\vec{x}$$

If the total energy given by your fuel is $E$, then:

$$E = W_{drag} + K.E_{car} + W_{friction} + W_{other}$$

Each of these terms vary different with velocity. Moreover, the efficiency of the engine changes with the speed of rotation and the gear with which you drove at.

There simply isn't such a cute relation between distance travelled and fuel consumed.