Seems like the first connection attempt to a new host is dropped; could be malicious, could be misconfiguration of one of their "magic boxes". A VPN should sor

Seems like the first connection attempt to a new host is dropped; could be malicious, could be misconfiguration of one of their "magic boxes". A VPN should sort this out, worst case the first VPN connection attempt will fail just like everything else, but the second attempt will work; once you have your VPN up all traffic should flow just fine within it, and no more problems.