I would say that your company is on very dodgy ground there if they try to claim VAT on the fuel. That's because they are not paying for the fuel. They most likely pay you a fixed mileage rate (45p per mile is normal), and they can fully deduct that as an expense. If they tried to deduct what they pay you, and deduct the VAT on the fuel, they should just hope that HMRC doesn't find out.
To make it more obvious why it would be illegal: If the company purchased a computer for £1,000 + 20% VAT = £1,200, they pay out £1,200, and they can deduct £200 VAT immediately, and £1,000 over a few years writing off the computer, so the total deduction is £1,200. In your case, apparently they want to deduct the money they paid you, plus VAT on the fuel which they are not paying, so the total deduction would be more than they paid. HMRC will be very, very unhappy to find this. Sorry, they will be very, very happy :-) For non-UK readers: HMRC = Her Majesty's Revenue and Customs; UK tax office.
What makes it worse is that the fuel is most likely used for business and for your private use, so they would be trying to reclaim VAT on fuel that wasn't used for business at all.
As far as you are concerned: You can safely give them your fuel bills if they ask for them and you don't mind; you're not their accountant and not responsible for how they handle their taxes. If you don't have the bills or don't want to hand them over, and they cause you trouble, then you might tell them the rest of this post. Myself I have never heard of anyone checking fuel bills.