Further investigation with the Windows client:
- Querying the IIS default page of the Remote Desktop Gateway Server works fine
- netstat shows an established HTTPS connection from the client to port 443 on the Remote Desktop Gateway when a connection attempt is made
- Replacing the FQDN of the Remote Desktop Gateway with its IP-Adress in mstsc.exe results in a "certificate and host name do not match" error when trying to connect
Out of ideas.