Esta é uma ótima pergunta. Tivemos um problema com o O365 há muitos meses, quando a ferramenta de sincronização do AD fez com que todas as nossas caixas de correio fossem excluídas. Levou quase uma semana para a MSFT restaurar todas as caixas de correio para nós. De qualquer forma, eles recomendam fazer backups fora do local, já que, em última análise, eles não são responsáveis pela perda de dados, a não ser o que está no SLA.
Trabalhamos com o MessageOps, pois eles têm uma ferramenta para download caixas de correio administrativamente que funciona muito bem. É grátis se você os listar como seu parceiro de registro no O365.