I can confirm that network profile is the key of the problem:

if you set the registriy value HKEY_LOCAL_MACHINE \ SOFTWARE \ Microsoft \ Windows NT \ CurrentVersion \ NetworkList \ Profiles \ [PROFILE] \ Managed to 1 then it works, mstsc will check for the RD Server before trying the GW. If it is set to 0 then it will not try to connect to the server, even before prompting for credentials.