I have a MasterCard debit card with which I never, ever had problems making payments and I have made such payments, either direct or through PayPal, Google Wallet or iTunes. Before this I had a Visa debit card issued by the same bank (Groupe Société Générale). Before this I had another debit card issued by another bank.
All of them worked, all of them debit cards, as indeed credit cards are not really popular here. Should mention that I'm from Romania and this debit card is linked to my bank account (are you talking about anonymous debit cards or something?).