They are a bank in Europe, just not the US. Sounds like the whole legal status in the US is a bit of a mess really:
"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.