Blockbuster wasn't damaged by all the ill-will they created by charging absurd, usurious late fees. They were the king of their realm, as PayPal is now.
But, making your customers loathe you turns out to be a bad idea in the long term. The very moment reasonable alternatives present themselves, those customers are gone for good.
PayPal has done a lot of legwork, especially for international commerce. But this legwork can and will be done again one day – or, someone will discover an interesting workaround that makes this legwork unnecessary for some specific but perhaps very common cases. Human ingenuity is inevitable, especially with such rich rewards waiting.
Either way, PayPal won't enjoy its position forever. Unless they turn these perceptions around, it'll be hard fall.