Você verificou as opções avançadas do mstsc? Conectei-me suavemente a máquinas com conexões de 1m / 250k.
Na guia "Experiência", você pode optar por desabilitar certos aspectos da área de trabalho remota. Existem até pré-ajustes para conexões ruins. Eu escolheria a predefinição mais baixa (modem 56k) e depois mudaria a cor para 15 ou 16 bits.