Success, but it may not be for everyone....
OK, after a lengthy discussion with my hosts and various tests by myself and great support by them, they too agreed that it is Paypal blocking the server. Paypal STILL deny this and blame the site scripts yadda yadda yadda.
Anyways, long story short, migrated site to a new server, which was tested to be communicating with api-3t.paypal.com (thanks symanski) before the switch and hey presto, works like a dream now.
Now, I believe any host worth anything should be able to do this for you too, as long as you can supply them with the Paypal server (api-3t.paypal.com) that the site is trying to communicate with then they should do it. Because this is a manual operation, they wont do it unless YOU give them the info. Also, ensure that nothing in the site is referenced to an IP address otherwise it will go a bit wobbly.
Hope this helps for some people if not everyone. My hosts have also logged a complaint so surely they will be forced to do something, but I wouldnt bother contacting their "support" team, I think they are contract bound to blame everything but Paypal.