I'm curious to which extent this is legal. I'm pretty sure a bank isn't allowed to block access to your accounts without a formal request from a legal entity.
Paypal doesn't "own" the money. This sounds to me as extremely abusive.
Is that this frequent?
It seems like the latter, but that seems to indicate that the legal systems of the world are fundamentally broken.
They were also sued in 2002 over the same issue, and settled in 2004 for the rather small sum of $9m, though they did also agree to modify their hold policy as part of the settlement (whether they've followed the terms of that agreement, I don't know): http://www.settlement4onlinepayments.com/injunctive.pdf
"Concern about Luxembourg's banking secrecy laws, and its reputation as a tax haven, led in April 2009 to it being added to a "grey list" of nations with questionable banking arrangements by the G20." [http://en.wikipedia.org/wiki/Economy_of_Luxembourg#Banking]
So, in effect, Paypal is probably a bank in nominal terms only. They can still do pretty much whatever they want with your money and get away with it. That is why my company went with WorldPay even when we started out. We don't get charged any fees, just commission, and we get free fraud insurance on the major credit cards.
You can't be a bank "in nominal terms only" in Europe. Once registered as a bank you are bound by EU and Member State laws. There's no sidestepping that. Governments can't sidestep them.
The fact that Paypal is registered as a bank in a European Member State means that they must abide by these laws and the regulation that goes with it.
Remember, loser pays in European courts. So when a bank steps outside the law, it will be liable for costs and "damages". It is not in their interests to break or even "stretch" the law.
Regardless, I wouldn't do business with Paypal if you paid me. Well, perhaps I would, but pay it straight to my bank, and not via Paypal.
P.S. My fight goes on: this week I have been active again in the European Parliament with MEPs fighting to get the appalling ACTA spiked. Something we should all be aware of and striving to kill.
Edit: mattmanser got there first.
As for the 'virtual money', it's not virtual, it's real. They run what is technically called a wallet system.
A real merchant account is of course an option, but the transaction fees can be quite high, there is the charge-back risk and a whole pile of regulatory hoops to go through before you can get that to work. Larger scale businesses have plenty of users for who credit card use is not an option. Large parts of the world are relatively free of the credit card plague and so can not pay you using your merchant account. For those situations paypal (or something like it that does not have paypals drawbacks) is a solution.
It's simple to explain: Paypal isn't a bank.