Parece que há um bug no Gerenciador de Credenciais do Windows 7 que causa esse comportamento. Depois de muita pesquisa na Internet, encontrei algumas soluções feias, mas também encontrei uma ótima:
No Gerenciador de Credenciais, adicione uma entrada para o servidor remoto, mas em vez de adicionar apenas o nome do servidor, como database.contoso.com, adicione o nome do servidor com a porta do SQL Server, da seguinte forma:
database.contoso.com:1433
Isso resulta no comportamento desejado, sem dor!
Fonte: link
Lembre-se também, é claro, que você precisa prefixar o nome de usuário remoto no Credential Manager com o nome do domínio remoto, da seguinte forma:
banco de dados \ administrador