Cada caso é um caso. Primeiro, você tem que saber que há basicamente duas formas de ler seus emails:
* online - É o caso do Yahoo!, Hotmail e GMail, que permitem que você leia seus emails pela página web, no próprio navegador (Internet Explorer, Opera, Firefox).
* offline - Usando programas gerenciadores de email, como Outlook e Eudora, você baixa (copia para seu computador) as mensagens e pode ler suas mensagens sem estar conectado na internet.
Cada webmail tem sua forma de tratar as correspondências excluídas. Geralmente, você pode configurar se quer enviar as mensagens excluídas pra Lixeira ou não. No Yahoo!, por exemplo, os emails vão pra Lixeira e são apagados de tempos em tempos (uma semana, muitas vezes menos).
Quando você usa o gerenciador de emails é a mesma coisa: vai de acordo com a configuração.
Resumindo: é melhor você forçar a memória e tentar lembrar quem mandou a mensagem pra você, porque se você já apagou, ela já deve ter ido pro beleléu faz tempo. Não tem busca avançada que dê jeito.