Se nelle impostazioni server hai anche impostato di svuotare il cestino all'uscita, oppure "Elimina subito i messaggi", oppure una cartella del cestino che non sia su cartelle locali, non c'é più posta eliminata.
Il Cestino in cartelle locali, è il cestino in cui va a finire la posta se spostata manualmente, o dagli account pop se usi la global inbox.
La peculiarità di imap è quella di tenere la posta sincronizzata su tutte le postazioni: quello che sposti, marchi come letto o cancelli su una, viene visto così su tutte.
Controlla di aver sottoscritto tutte le cartelle necessarie.
Dovresti tentare, come ultima risorsa, di accedere via web alla tua casella di posta, e vedere se c'è ancora qualcosa nel suo cestino.
Controlla anche se ci sono due cartelle Trash sul web (dovrebbe essercene solo una).