La cosa migliore è cercare tramite tim mail lato browser, perchè i client tipo Outlook a volte hanno delle policy che limitano la ricerca.
Per esempio io su outlook non vedo le mail più vecchie di tre mesi a meno di non forzarne la ricerca.
Devi verificare due cose:
1- se il tuo client cancella le mail lato server una volta scaricate (ormai non lo fa quasi più nessuno). Se così fosse e per qualche motivo si è cancellata su Outlook (anche dal cestino) allora è persa per sempre
2- se così non fosse allora cerca direttamente sul server tramite il tuo browser verificando anche cartelle spam e cestino. E' più sicuro. Se non le trovi nemmeno così la vedo dura a meno di non contattare il provider e sperare che abbia fatto di sua iniziativa dei backup periodici. Quasi sicuramente li hanno perchè per legge sono obbligati a fornire alla Polizia postale in caso di richiesta per un tot di tempo le info su tutto ciò che transita sui loro server. E' però difficile che li diano a te, anche se sei il proprietario della casella di posta.
Ovviamente se le mail avessero un altro destinatario oltre a te puoi chiedere a quest'ultimo di rimandartele, ma penso che a questa possibilità ci abbia pensato anche tu.
Sono cosi avanti che quando guardo indietro vedo il futuro.