Depois de tentar muitas técnicas, o que finalmente acabou corrigindo foi excluindo a conta no azure e criando uma nova. Postando isso aqui porque não conseguimos encontrar essa resposta simples em nenhum lugar.
Algumas coisas a destacar:
- Parece que o Azure é exigente quanto ao SendGrid ter que ser provisionado dentro do Azure e não funciona bem com contas do SendGrid provisionadas dentro do SendGrid.
- A conta anterior foi originalmente provisionada dentro do Azure e estava funcionando originalmente, mas parou de funcionar por algum motivo. A única coisa que fizemos de maneira diferente foi modificar os subutilizadores, adicionando um novo "membro da equipe", que pode ter invalidado de alguma forma o usuário especial do azure. Ou é possível que tenha havido alguma outra questão fora do nosso controle.
- A conta anterior que parou de funcionar não estava aparecendo em Todos os recursos no Azure, mas estava aparecendo nas contas do sendgrid. A nova conta apareceu em ambos.