Let me try and summarise what I believe is happening - please feel free to correct me if I'm wrong
- When you were with TalkTalk you were unable to get to Paypal of Ebay websites, as the public IP being used to reach those sites was blocked by destination (Paypal + eBay)
- You changed to Zen ISP and the same issue continues
It does seem odd that both ISP's have issued you with an IP that is blocked by these sites. It is also odd that you couldn't use any VPN software on a device to circumvent this. When you connect to a VPN they are essentially proxying the traffic for you. I don't see why an ISP would block VPN usage. Put that together with the fact their public IP's are on block lists for 2 major websites, it doesn't sound like a very professional setup.
I will throw one more thing into the discussion and that is NAT (Network Address Translation). ISP's need a lot of public IP's to issue to their customers. If you are a small ISP then you may not have enough public IP's to give each customer their own IP. Therefore you can NAT the traffic for one IP to many IP's behind it solving the problem. The issue with this is that you now have lots of people using the same public IP to make requests to websites. The webserver receiving lots of requests from the same IP address will generally think all these hits coming from one source is malicious and then rate limit or block it. THIS is what I suspect has happened to Zen internet, probably because they are a small outfit. Why the same happened on Talktalk and why you are unable to use a VPN is a mystery to me. Zen really don't sound like a great company, I hope for your sake they were very cheap. I wouldn't stay with them if it were me.