It is a common issue for French people renting cars outside of France - search on Google, there are hundreds of angry people who ended up with no car because agencies in other countries refuse debit cards (debit immediat)
I should have been more specific, In the past few years I have rented cars in Europe, in the US, in South Africa and in Australia. Never had an issue. I generally use Avis or Budget, sometimes a local company.
