può darsi che la polizia postale recuperi mail cancellate dal cestino attraverso qualche server di backup di chi gestisce la connessione internet (solo se ci sono indizi di reato, procedimenti penali in corso), oppure utilizza programmi particolari che non conosco (ho dato un'occhiata in rete ma sembra non esistano software per recuperare mail cancellate con la webmail di libero, il che ha un senso dato che viene gestita tutta col browser)
prova a controllare i file temporanei/cache del browser (vai nelle opzioni), per verificare se c'è ancora qualche pagina web dove tu avevi aperto le mail che ti interessano
comunque la questione è sempre la stessa, se gli indirizzi vengono salvati automaticamente nella rubrica dovevi stare più attenta, ed eliminare ogni tanto gli indirizzi inutili dalla rubrica
quindi sì, intanto fai pulizia nella rubrica ed elimina tutti gli indirizzi che non ti servono
poi controlla che non ci sia abilitata un'opzione per salvare in automatico gli indirizzi (non conosco la webmail di libero), se c'è toglila, in questo modo la tua rubrica non rischierà più di raggiungere il limite massimo di voci, e dovrai scegliere tu ogni volta se aggiungere o no nella rubrica l'indirizzo
a meno che tu sia una persona non molto precisa e meticolosa, come potrebbe far supporre l'aver lasciato la rubrica riempirsi di così tante voci, in questo caso consiglio di lasciare l'inserimento automatico dell'indirizzo in rubrica, pulendola periodicamente