just like ebay became the second or third largest exportation market from chinese autonomous regions while no one was looking, paypal has become a gigantic international bank holding company while no one was looking. apparently they've managed to dodge regulatory supervision in the US, but in the EU and in most other reasonable countries, they've been forced to set up house as a regulated banking organization.
the consequence of this is that the international paypal conglomerate has a lot of assets in many currencies. when they reach critical mass in their holdings in two currencies (eg, CAD and USD) that matches their transaction bulk between those currencies, they can charge a lower fee because they are just shifting money between the currencies on paper (although i'm sure they're forexing the crap out of the currency markets 24/7), entirely in their internal accounting and not actually having to exchange between currencies.
however, when their holdings in two currencies don't match the transaction bulk, they are actually going to have to forex for functional reasons to make the payment happen for the users and not just to make money hand over fist. when that actually happens, i'm sure they're passing on the hefty fees involved to the consumers and then some.
heck, the fact that they skim 3% on USD to USD transfers when there's no swipe fee involved (and god knows their agreements with visa and amex when they _do_ have to draw from a payment system are very very generous to paypal) is completely insane as it is. hand over fist, folks.