Stegzilla,
A resposta a essa pergunta deve ser fácil, mas pode ser difícil. Na minha experiência com esta ferramenta como um contratante da Microsoft, parece que tentar reutilizar o registro do servidor antigo (como no backup que você restaurou) não vai funcionar. Isso corrompe o registro.
A única maneira de corrigir esse problema é uma nova vm com o sistema operacional instalado a partir de uma nova imagem ISO e não um backup ou um clone. Obtenha um novo download da versão mais recente da ferramenta do Exchange Online ou do Azure Active Directory em users > usuários ativos. Será no topo da página.
Isso deve ajudar.