Parece que Michael estava certo - e apesar de o Windows suportar Teredo fora da caixa, quem está do outro lado desse túnel não suporta a Microsoft.
Após se inscrever em um túnel com HE e executar seus comandos de configuração, funcionou instantaneamente e a Assistência Remota Easy Connect também pôde se conectar.