I was finally able to resolve this and it seems it´s a Certificate Issue regarding the VPN Pulse Secure is trying to connect.
What I did:
1- Went to Chrome (or IE, depending where do you have that Certificate) and unistalled the Certificate.
2- Downloaded and executed the .cmd completed installation process. While doing this, in one of the steps (not sure if you would have something similar) I had the option "Enable Strong Key Protection" -----> Un-clicked it, it seems it ends causing trouble.
3- After that, I:
a) deleted the VPN settings.
b) went to "connections" in Pulse Secure ----> "Forget Saved Settings"
c) Recreated the new VPN settings
After that, It connected at the first try.
Interesting.. I get this same problem on OSX. It is very frustrating. It "magically" went away for 2 months.. and today now its back. I'm using a yubikey -- so your trick of reinstalling a certificate won't work..
I tried stopping pulse, starting it, logging in, all within 25 seconds.. and it still gives the timeout error.
BTW.. Pulse 9.0.2 (1151) and OSX 10.14.1
I am wondering if an ipconfig /flushdns will resolve the issue.