A solução que acabei indo era executar o serviço como usuário local.
Isso significa que eu poderia fazer login na área de trabalho desse usuário e executar manualmente o mstsc
, onde, com certeza, um aviso "tem certeza" apareceu.
Depois que marquei a caixa "não me pergunte novamente para conexões com este computador", a execução do meu serviço nesta conta de usuário funcionou corretamente
Também pode ser possível adicionar a entrada correta ao HKCU\Software\Microsoft\Terminal Server\Client\LocalDevices\
do SYSTEM para evitar a criação de uma nova conta, mas para mim a conta sem privilégios parece melhor em geral.