While that may be true, Luxembourg is known as a tax haven. I note that Amazon also registers its European operations there. From the same source as you cited:

"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.