Ich glaube, du musst einfach den Posteingang öffnen, alle Mails markieren und dann <rechtsklick> wiederherstellen.

Ist bei mir schon so lange her, dass ich es nicht mehr genau weiß, sollte aber so klappen (entsprechend auch mit den anderen Ordnern)!