There are Visa debit cards. I have one. I have not had problems paying anyone with it.

[EDITED to add two other things:]

I don't know how readily available Visa debit cards are in Austria; perhaps your bank offers only some different variety of debit card.

In the UK, at least, there are regulations around credit cards that don't apply to debit cards and that give buyers considerable reason to prefer paying by credit card even if they have no need to borrow. Specifically, if you buy something with a credit card then a piece of legislation called the Consumer Credit Act makes your credit card company liable (as well as the seller) if the seller fails to meet the terms of their contract with you. So, e.g., if you buy something with a credit card and then they just don't deliver, or they go out of business, you can get your money back from the card company. So there's a big advantage to using a credit card for substantial purchases. Again, this may be different in Austria.