That is a very good point. My original question disregarded non-essential travel, imagining fuel as a fixed-consumption good. This is what I meant when I referred to it as a 'staple;' I'm unfortunately failing to recall the term for a good with an inflexible rate of consumption.

However, even though fuel is not fixed-consumption, it seems that this policy would also depress travel; taxing the mileage should discourage people from traveling in a similar way to taxing the fuel.

  A better question would be "Wouldn't taxing miles instead of fuel also bend the market and depress travel? If it would, why not just keep taxing fuel, since we already have a system in place to do so?"

It seems to me that if you tax a staple good, and people will be consuming less of that staple good due to an increase in efficiency... meaning you'll bring in less money from those taxes...

Then you raise the tax. What's the downside? It's not like people are going to consume less gas if the tax goes up.

Arguably, cranking the tax could also lead to people holding onto junker cars for sentimental reasons replacing them or repairing their engines. So really, it's win-win.