Fuel duty works out at about 5p/mile. Slightly more for thirstier vehicles, slightly less for lighter vehicles.

There is zero need to implement anything for petrol or diesel vehicles, which nicely eliminates the "pre-2016" problem (How many 10 year old electric vehicles are there? Not enough to worry about). I'd be inclined to provide a government API, and require the manufacturers to provide the data in a specified format. Make it part of type approval for use on the UK roads.

Not impossible, nor should a VIN + Mileage number be particularly risky for privacy concerns - the number should be pushed regularly, to prevent wind-back tricks.

15p/mile has got to be a joke though. That'd be the equivalent of setting fuel duty to £1.50/litre - it would immediately shag what's left of the economy.