A solução foi gerar meu certificado novamente, desta vez forçando o RSA e o SHA1 (embora o SHA1 seja o padrão, de qualquer forma). Por alguma razão, o Win Server 2k3 não podia ou não usaria as cifras corretas com um certificado makecert padrão. Aqui está a linha de comando que funcionou para mim:
makecert -pe -r -ss my -sr localMachine -n "CN = nome_do_domíniooripaddressgoeshere.com" -e 01/01/2098 -a sha1 -eku 1.3.6.1.5.5.7.3.1 -sky exchange -sp "Fornecedor Criptográfico Microsoft RSA SChannel" -se 12