Isso acontece de forma um pouco aleatória com os cartões do MBNet no Paypal.
O que tenho notado é que em pagamentos diretos de baixo valor, <20 euros, isso quase nunca acontece mas para valores superiores é cada vez mais comum.
A única alternativa é criar uma conta paypal, associar o cartão MBNet (com os custos e incómodos inerentes à situação) e só depois fazer o pagamento. Desta forma o pagamento é 99% das vezes aprovado.
É pena que os gigantes dos leilões e retalho continuem a utilizar quase exclusivamente o Paypal, com todos os seus defeitos e regras "obscuras".