Olá, David.
Pelo que você descreveu e pelas informações apresentadas, o problema parece estar relacionado a uma possível alteração não autorizada das informações de segurança da conta Microsoft. O fato de você ter recebido uma mensagem informando que uma chave de acesso foi removida, sem ter realizado essa alteração, é um ponto importante.
Como você também informou que o e-mail de recuperação, o autenticador e o código de recuperação não estão mais disponíveis, o ideal é seguir o processo de recuperação da Microsoft sem tentar excluir a conta neste momento.
1. Não exclua a conta agora
Neste momento, eu não recomendaria solicitar a exclusão da conta.
Primeiro é necessário tentar recuperar o acesso e verificar se as informações de segurança foram realmente alteradas por terceiros. Se a conta ainda estiver vinculada ao seu número de telefone, isso pode ser útil durante o processo.
2. Verifique se existe uma alteração de segurança pendente
Um dos pontos mais importantes do seu relato é a possibilidade de os métodos de segurança antigos terem sido removidos e substituídos por outros.
Quando as informações de segurança de uma conta Microsoft são alteradas, pode aparecer uma mensagem informando que a alteração das informações de segurança está pendente.
Esse processo pode permanecer pendente por até 30 dias.
Se você encontrar essa mensagem e não foi você quem solicitou a alteração, procure na própria tela a opção semelhante a "avise-nos" ou uma opção indicando que você não realizou aquela alteração.
Isso é importante porque permite informar à Microsoft que a mudança não foi autorizada por você.
3. Utilize o Assistente de Entrada da Microsoft
Como você não possui mais acesso ao e-mail de recuperação, ao autenticador ou ao código de recuperação apresentados pelo sistema, recomendo utilizar primeiro o Assistente de Entrada da Microsoft.
Informe o endereço de e-mail ou telefone que estava associado à conta e siga as etapas apresentadas.
Esse procedimento é especialmente indicado quando:
as informações de segurança foram modificadas;
a conta apresenta comportamento diferente do habitual;
você não reconhece determinadas alterações;
ou acredita que outra pessoa possa ter obtido acesso à conta.
Se o Assistente de Entrada não conseguir resolver o problema, o próximo passo é utilizar o formulário oficial de recuperação da conta Microsoft.
Nesse formulário, tente fornecer o máximo possível de informações que comprovem que a conta pertence a você.
Sempre que possível, faça o preenchimento utilizando:
o mesmo computador que você costumava utilizar;
o mesmo navegador;
uma localização normalmente utilizada para acessar a conta;
senhas antigas que você se lembre;
informações antigas da conta;
contatos para os quais você enviava e-mails;
assuntos de mensagens que você enviou;
informações relacionadas aos serviços Microsoft que utilizava.
Mesmo que algumas dessas informações sejam antigas, elas podem ajudar na tentativa de comprovar a propriedade da conta.
5. Sobre aparecer que a conta "não existe"
O fato de um aplicativo informar que a conta não existe não significa necessariamente que a conta foi excluída.
Como houve alterações nas informações de segurança, pode haver diferenças na forma como os serviços estão identificando a conta.
Por isso, eu não concluiria ainda que a conta foi apagada.
Primeiro é necessário verificar a situação por meio dos mecanismos oficiais de recuperação.
6. Sobre o código estar sendo enviado para um e-mail que você não reconhece
Isso também merece atenção.
Se uma pessoa conseguiu alterar os métodos de segurança da conta, é possível que os códigos de verificação estejam sendo enviados para um método que foi adicionado posteriormente.
Nesse caso, o problema não é simplesmente "esqueci minha senha". O problema passa a ser recuperar o controle dos métodos de segurança da conta.
Por isso, não recomendo ficar tentando várias combinações de senha ou cadastrar repetidamente novos métodos de segurança antes de concluir o processo de recuperação.
7. Faça uma verificação no computador
Como houve um possível acesso não autorizado, também é importante verificar o computador utilizado para acessar essa conta.
Antes de alterar novamente a senha, faça uma verificação completa contra malware usando a Segurança do Windows ou outra solução de segurança confiável.
Isso é importante porque, se houver algum programa malicioso capturando senhas ou sessões de navegador, simplesmente trocar a senha pode não solucionar o problema.
Também vale verificar extensões instaladas no navegador e remover qualquer extensão que você não reconheça.
8. Depois que recuperar a conta
Se conseguir recuperar o acesso, faça uma revisão completa da conta imediatamente.
Verifique:
senha atual;
métodos de autenticação;
número de telefone;
e-mail de recuperação;
dispositivos conectados;
atividades recentes de login;
aplicativos autorizados;
contas conectadas;
regras de encaminhamento do Outlook;
respostas automáticas;
contatos e configurações que tenham sido modificados;
métodos de autenticação que você não reconhece.
Remova qualquer informação ou dispositivo que não pertença a você.
Depois disso, configure novamente os métodos de segurança que você controla e, se possível, mantenha mais de uma forma de recuperação.
Também é recomendável gerar um novo código de recuperação e armazená-lo em um local seguro.
No seu caso, eu seguiria esta ordem:
1. Não exclua a conta.
↓
2. Utilize o Assistente de Entrada da Microsoft.
↓
3. Verifique se aparece alguma mensagem informando que a alteração das informações de segurança está pendente.
↓
4. Se você não realizou a alteração, procure a opção "avise-nos".
↓
5. Se não conseguir recuperar o acesso, utilize o formulário oficial de recuperação.
↓
6. Preencha o formulário utilizando o máximo possível de informações antigas e verdadeiras da conta.
↓
7. Faça uma verificação completa do computador contra malware.
↓
8. Depois de recuperar a conta, altere a senha e revise todos os métodos de segurança, dispositivos, aplicativos e configurações do Outlook.
Um detalhe muito importante: se a conta estiver com verificação em duas etapas ativada e você não possuir acesso a nenhum dos métodos alternativos cadastrados, o processo de recuperação possui limitações e pode não permitir simplesmente substituir esses métodos por um novo.
Por isso, no seu caso, eu daria atenção especial à possibilidade de existir uma alteração das informações de segurança pendente. Se essa mensagem aparecer, e você tiver certeza de que não foi responsável pela alteração, utilize a opção para informar à Microsoft que não foi você quem realizou a mudança.
Pelo seu relato, o mais importante agora é recuperar a conta e recuperar o controle das informações de segurança antes de pensar em excluir qualquer coisa.