I recall a discussion of this point on HN a long time ago, but GPS is only one way to charge taxes based on vehicle miles traveled (VMT) - another, which is less invasive, is just to read the vehicle's odometer on some regular basis, either by hand when doing an annual vehicle safety inspection, or automatically by having the vehicle transmit the data. Certainly those have risks of tampering, but so does GPS.

Or report your odometer reading every time you renew your registration with steep fines for lying.

Or simply add a tax on new cars. Those who drive a lot will have to replace their vehicles more often and pay more tax.

Taxing newer, more fuel efficient vehicles is counter productive.