Well, we're not getting all that many customers yet so it's hard to give you a percentage. I also don't receive a notification every time this happens. It's only when the customer contacts us about his problem that I can ask him what it is exactly that is happening.
However, I can tell you that so far this has happened with all of our UK based customers (which are only really a couple), all using regular Visa cards.
Our Paypal account is a verified Business Account with a limit of 2500 euro. The limit shouldn't be a problem though, as we haven't nearly reached it yet.
Like I said, the problem doesn't seem to occur when the customer actually has a Paypal account that they can log into. It's only when trying to pay through Paypal without an account. It's getting pretty frustrating, especially since there doesn't seem to be anything that I can do to solve it on my end, and also because I haven't been able to pinpoint what exactly causes this.
I'll look into Sagepay, thanks for the recommendation.
EDIT: okay, Sagepay is out of the question. We're not making enough revenue through our webshop yet to justify paying 25 quid a month for the Gateway. Unless I misinterpreted something?