You know how every time a new payment provider comes up and people kvelch that it isn't available in their country and how no provider is? This is because every payment provider which attempts to hit as many countries as Paypal does dies. They're killed by fraud. (Fraud kills domestic ones, too, all the time, but it's marginally less frequent.)
Luckily, Paypal is an anti-fraud AI company which also happens to run credit cards sometimes. When in doubt, they will always come down on the conservative side. This is why they still exist. (Early in their corporate history they lost -- no kidding -- one hundred million dollars to fraud.)
This perception does not actually match reality, though: most people bitten by this are unaware that similar activity would get them shut down by the fraud department at e.g. a bank. See comments by dangrossman, etc.