In principle I would agree with your supposition that VAT is the way to go. I suggested it last year, but as I now understand it, Fuel tax is "Duty" and comes under different international tax rules, so therefore VAT, which is essentially a purchase tax, would probably not satisfy the EU's appetite for Fuel duty harmonisation and would also distort the EU VAT picture if levied heavily.
There could also be problems with international distribution and reclamation of VAT if the VAT on fuel in the UK is highly biased, which is supposed to even out over all member states.

Steve.