@blaker After reading this post: Elastic Agent 7.14 -- Strange bug during enrollment "Elastic fleet agent bug" it seems we are experiencing similar problems.
Furthermore I can confirm that we are having this problem on Windows Server 2016/2019 but NOT on Windows Server 2012.
We have two machines behind the same network, one running Windows Server 2012 which enrolls properly and one running Windows Server 2016 which fails to enroll.
I hope this can help !
Cheers