Same issue here in Kansas City. Kansas' gas taxes are higher than Missouri's so a lot of people buy gas on MO side.

I think Oregon also said that the large number of hybrids in the state is pushing them towards a per mile tax, but I think their implementation is a straight per mile tax (I haven't checked the proposal so this could be wrong) which would discourage hybrid purchases.

Texas (and large portions of the other parts of the country) is going the toll road route. You're charged every so many miles for driving on the toll roads, unfortunately the electronic system they have in place is as privacy lacking as the GPS suggestion (although you can put the RFID tracker in a case to block detection).

I'm not sure there is a good solution. Most states have an inspection requirement on cars and an emissions requirement. Perhaps a fee based on milage change since last inspection, with rewards if the actual emissions of the car are below certain levels. Not all the milage would have been driven within that state but is that a significantly high amount to worry about (for residential cars at least).

But to be honest, Americans seem to ignore any effort to move from the car to mass transportation. I think we'd start moving to it if the price of gas doubled from what is now, but I'm not even convinced of that.