OK I have narrowed down the issue.
The host I'm running PowerCLI on has no internet access, but it can still get internet name resolution (DNS) and ping hosts on the internet, port 80 to the internet is completely blocked though.
I've run a Wireshark capture when starting up PowerCLI and you can see that even though 'Check for publisher's certificate revocation' is disabled it is still trying to communicate to something on the internet. The source port is 59338, destination is 193.45.10.136 port 80 and of course this communication fails.
If I disconnect the network card PowerCLI starts in 3 seconds, with the network card enabled it takes 17 seconds! So there is definitely still some communication being attempted which is causing PowerCLI to take longer to startup, does anybody know what this is and how to disable it?
I know I could probably workaround this by disabling internet name resolution but doing so for this host only will not be easy, better if I can simply disable whatever is still trying to communicate to the internet when PowerCLI starts.