It's not a matter of hosting company, but individual IP addresses, at least in my case.
They moved my site to a different address and now paypal works fine!!!
I'm just lucky that it happened on a new site that I had just launched and I only lost 1 or 2 sales.
The hosting company I use respond to tickets within a maximum of 10 mins, and moved server without any problem, just had to wait for a quieter time for them to do it.
I don't think hosting companies are to blame, the one are use are not the cheapest, although not expensive either, but very realiable.
One possible suggestion is that they had someone banned by paypal/ebay hosting a site, but it seems too wide a problem, and too silly of PP to block entire IP addresses.
Looking at things from another angle, are Paypal blocking Prestashop shops? Could it be that it was our Prestashop site that caused PP to block the IP? Maybe Prestashop is blacklisted by PP (not saying it is, it wouldn't make sense to me, just putting forward a possible explanation). Maybe we can ask our host if this has happened before to them? The block happened a few weeks after I launched a new shop,
Also interesting to know how, at least in my case, Paypal and eBay both blocked the IP.
On a different note: what do I need to change on Prestashop after moving server? Orders are going through ok.