Olá, entendo a urgência.
Primeiro teste pelo navegador, não pelo aplicativo: acesse https://outlook.live.com, entre na conta e pesquise o e-mail usando palavras-chave, remetente ou data, por exemplo: after:2019/01/01 before:2020/01/01.
Verifique também as pastas Arquivo, Lixo Eletrônico, Itens Excluídos e “Recuperar itens excluídos desta pasta”. A Microsoft explica este procedimento aqui: https://support.microsoft.com/outlook/mail/recover-and-restore-deleted-items-in-outlook
Se o e-mail só não aparece no aplicativo, pode ser limite de sincronização/cache. Nesse caso, remova e adicione a conta novamente ou teste no Outlook Web.
Se também não aparece no Outlook Web e foi excluído há muito tempo, infelizmente pode não ser mais recuperável, pois itens removidos dos excluídos normalmente só ficam recuperáveis por período limitado. Nesse caso, abra um chamado pelo próprio Outlook Web em Ajuda > Contatar suporte, para a Microsoft verificar a caixa no servidor.