As suggested, Paypal is generally safe. At least, noone other than Paypal has access to your cc details, so vendors &/or 3rd-parties (hackers, etc) cannot skim the account.
Another alternative is to use a virtual credit card, which some banks offer. Some virtual cards allow the user to set the total dollar amount &/or a time-limit for each transaction (by default, most virtual cards auto-expire at the end of the month), so any subsequent charges against that card number are automatically ignored.
I use a virtual credit card with Paypal, which provides pretty bullet-proof protection. Everything I purchased by phone or online over the past 7-8 years was done with a virtual card. Pizza, utility bills, watch parts, all done with a virtual card. If I carried a smart phone or computer with me, I would probably use virtual cards for everything & leave my real card at home.
By the way, another possible, albeit less likely, scenario is that r8247's card got skimmed wirelessly by someone local. With the right equipment, a clever hacker, restaurant employee or store clerk simply scans the magnetic strip on your card as you pass them by. The only foil against this type of threat is to store your card within a Faraday cage (grounded metal container).