Você pode realmente hospedar sua caixa de correio no Azure (mas talvez não queira), mas o problema a que você está se referindo não se refere apenas ao Azure, mas a qualquer provedor de hospedagem. Quando você compra uma caixa ou VM, pode ser que o IP que você recebeu tenha sido usado por outra pessoa antes. Se essa pessoa tiver sido um ponto para enviar spam de (intencionalmente ou não), o IP provavelmente será listado na lista negra. Parece que o Azure está tendo muitos problemas com a lista negra de seus IPs.
Então sugiro entrar em contato diretamente com eles para ver se ainda é um problema, se ainda houver, há muitas alternativas para o Azure.