We almost got our holiday ruined by that. Here in Norway, debit cards are the norm. I've never had an issue renting a car with a debit card. I've never had an issue using my debit card, even though someone else would be driving.
However, when we showed up at Budget on the Big Island of Hawaii to check out our reserved car, we quickly found out things were not the same.
My SO has a driving license but only a debit card. I had a credit card but no driving license. Since we were not from the US, they explained, the driver had to have a credit card. Mine wouldn't do.
We went to Avis next doors (unsurprisingly the owner of Budget), and was met with the same demand.
Our two week vacation seemed ruined before it got started, as there's hardly any bus service to talk about and we were quoted like $100 just for a one-way trip with a taxi to the place we'd be staying, and that was a "nice price" since we were in a pickle. We tried to call our bank back home to see if they could help us in any way, but predictably they couldn't. We asked if a sizable deposit would help, but no. Minute by minute we felt our dream vacation was turning into a nightmare as hope evaporated.
After a few rounds back and forth with the person behind the counter the manager sensed something was up, and after explaining our situation she asked where we'd be staying. We'd found an Airbnb-like place so it was a residential address, and she gave it a few seconds before she said to enter that along with my SO's debit card details. Vacation saved!