For the life of me I cannot understand anyone would use PayPal. I'd rather trust the postal system with an envelope of money. I have yet to see an area where there aren't better options.
But they take paypal also, so no bother. Do the transaction on paypal.
This kind of thing happens maybe once every couple of months for me, and is why I keep paypal around.
Edit to add: I think some UK banks are much more trigger-happy than the global average when it comes to flagging transactions as possible fraud. I once had to pay my tax bill (to the UK government) by paypal because the debit card transaction was declined.