I am not familiar on how KMS works but running it behind a proxy might need additional settings.
Moreover since KMS seems to use RPC, opening other ports might be needed not only in Google Firewall but also on your Windows VM.
I found awkward the authentication is failing even after adding an external IP. To isolate the issue there are a couple of test you could try:
Create a new network and a new server. See if that works.
Take a snapshot of the original servers that are failing to authenticate. From that snapshot create a new server in the new network and see if that works.
There could be a routing problem either in the original network or on the server configurations.
Google Compute Engine handles licensing for Windows Server when you create and start Windows instances. To activate a Windows VM they must have an external IP address assigned to them. The external IP address is required to activate a Windows instance with Google’s KMS servers. You cannot turn off the external IP for a Windows VM on Google Compute Engine as it requires re-activation every 30 days.
The NAT will not work as we need an external IP as the identifier to validate the Windows VM that is requesting the activation. We are actively working on a fix to address this issue and to make it so you can activate against VMs with internal IP only. In the meanwhile if you wish to restrict outbound communication you can set up egress firewall rules as follows:
Create a deny egress firewall rule for the ip range 0.0.0.0/0 on all ports
Create an allow egress rule to the ip 173.255.119.204 and the port tcp:1688. This will allow the VM to talk to the KMS Servers.
The allow rule should have a higher priority ( i.e. a lower number) than deny rule.
I am not familiar on how KMS works but running it behind a proxy might need additional settings.
Moreover since KMS seems to use RPC and opening other ports might be needed not only in Google Firewall but also on your Windows VM.
I found awkward the authentication is failing even after adding an external IPs. To isolate the issue there are a couple of test you could try:
Create a new network and a new server. See if that works.
Take a snapshot of the original servers that are failing to authenticate. From that snapshot create a new server in the new network and see if that works.
There could be a routing problem eihter in the original network or on the server configurations.