Tried again to import these certificates and now it works also for me. Previously I have imported the certificates only on the client machine where I use ePo console but NOT on ePo Server itself (shame on me). Today I have imported them on ePo Server and afterwards I was able to successfully install extension 126.96.36.1998 and it works like a charm. AP Policies and also rules are available.
Therefore I will mark Davids answer as correct.
Additional info: The certificates are available here > How to install the 2048-bit Code Signing root and intermediate CA certificates? | Symantec
Thanks for the update. I also did not think about importing the certs to the server. I did that and now AP policy properly shows up. Any idea why a 2012 R2 server wouldn't automatically get these Verisign certs as part of the Root Certificate Program?
one or more of the following: proxy authentication, proxy blocking, missing routes on firewall/blocked routes, domain GPO blocking updates
I'm sure there's more!
Guess that means it could be anything haha. It would be nice if there was a more descriptive error message because the one presented from the application and in the Orion log gave no indication that it could be certificate related.