Wie 30k richtig schreibt, arbeitet IMAP grundsätzlich auf dem Server (hat z.B. Vorteile, wenn man seine Mails von mehreren Geräten abrufen und auch immer überall den selben Stand haben möchte - genau deshalb nutze ich es z.B.). Das heißt aber auch, dass E-Mails, die gelöscht werden, tatsächlich auch auf dem Server gelöscht werden und nicht nur lokal (schließlich wird hier, wie erwähnt, nicht lokal gearbeitet).
Bei den meisten Mail-Anbietern werden gelöschte E-Mails dann in einen Papierkorb verschoben und können von dort wiederhergestellt werden.
Weitere Infos zum IMAP-Standard gibt's
hier und den dazugehörigen Update-Dokumenten ("Updated by").