Is there a solution to allow AcmeService to authenticate a user with SSPI if that user is in an external domain and there is no defined trust relationship?
Não.
Se estiver restrito a trabalhar com a classe .NET NegotiateStream, você verá na documentação do MSDN a classe NegotiateStream, [MS-NNS] :
The .NET NegotiateStream Protocol uses SPNEGO (which selects between Kerberos and NTLM) to determine the underlying security protocol to use.
Então, suas escolhas são NTLM e Kerberos.
[email protected] wants to authenticate too with AcmeService, but wants to authenticate with integrated security because he doesn't trust AcmeService enough to give away [his] password.
Bem, então o NTLM está fora. O NTLM v1, v2 e v2 com Segurança de Sessão dependem de algoritmos hash fracos e, além disso, os hashes da senha são essencialmente equivalentes a senha, portanto, concordo com você que usar o NTLM para autenticar um serviço é dar uma senha para esse serviço.
Então agora você é deixado apenas com o Kerberos. E o Kerberos, como implementado pelo Active Directory, não autenticará as credenciais de um domínio não confiável.
Então agora você não tem mais opções.
I think the general solution would be to create an outgoing trust relationship between ACME.COM and DISNEY.COM, but it is not possible in my scenario.
Você está certo de que a criação de uma confiança permitiria que um domínio Kerberos confie no mecanismo de autenticação de outro território Kerberos, mas, como você não pode criar uma confiança, você é SOL.
Quando você deseja fornecer autenticação strong e mútua entre um cliente e um servidor e não pode usar o Kerberos, use PKI, certificados digitais, TLS.
Normalmente, sugiro que você explore os Serviços de Federação do AD, mas provavelmente não será possível criar uma relação de confiança tradicional do AD por qualquer motivo, então você não poderá criar uma confiança de Federação.
Então, minha sugestão é de certificados de cliente. (Schannel)