Ok, consegui descobrir o que estava acontecendo e consegui uma solução alternativa.
Parece que há uma semana eles estavam tocando com a política de segurança do Windows. Eles estavam adicionando / removendo permissões, mas eles não podem me dar exatamente o que eles fizeram porque eles realmente não sabiam (ai!).
De qualquer forma, conectei-me usando a autenticação do Windows (-E switch) e executei a seguinte consulta:
ALTER LOGIN [sa] WITH PASSWORD='newpassword', CHECK_POLICY=OFF
GO
ALTER LOGIN [sa] ENABLE
GO
A chave aqui é CHECK_POLICY = OFF . Isso fez o truque. Espero que isso seja imune a mudanças futuras na configuração de seus domínios.
Obrigado por todas as suas sugestões.