While is it always EUR800? There's no option to simply reimburse their mileage (kilometerage?) ?
I.e. "You submitted your mileage report to the payroll department and it said you drove 214km on company business since last pay period, so your paycheck will have an extra 214 * 0.29 = 62EUR in it."
Actually, in the US it need not even be that complicated. If you are using your car for work purposes, you can simply claim the mileage once a year when you do your taxes. Company cars are, as you mention, mainly a status symbol for high-level executives, possibly including a driver. Even then, I've only heard about it in movies and books. All the real executives I am aware of just get paid enough that they can definitely afford a BMW if they want one.
[I use EUR0.29/km here because it is the US Federal mileage rate (54.4 cents per mile), converted for currency and units. With gasoline prices much higher (not sure about insurance, maintenance, etc) in Europe, I would imagine the reimbursement rate would need to be higher.]
Also, who pays for the gas? Do you get a company credit card for fill-ups?