Some days ago we experienced also problems when trying to pay for a bigger Mercury Licence by PayPal from Germany. Every try, our PayPal transfer (with own PayPal login) to Australia was cancelled with an unspecific error message. Then I have tried to transfer the amount as described without PayPal login. But also this doesn't work because PayPal wants that we create an own account immediately, as described by Albert. Now I'm in contact with David and finally he has send me an invoice - but unfortunately without any bank account data where we could transfer the money to. Presently I'm waiting for a new invoive from David.
The entire transfer procedure should be renewed and simplified that David gets his money in time. I think PayPal is a good solution in general, but Country specific problems should be checked in advance.