diff --git a/pykolab/imap/cyrus.py b/pykolab/imap/cyrus.py
--- a/pykolab/imap/cyrus.py
+++ b/pykolab/imap/cyrus.py
@@ -443,7 +443,7 @@
 
         mailfolder = self.parse_mailfolder(mailfolder)
 
-        undelete_folders = self._find_deleted_folder(mailfolder)
+        undelete_folders = self._find_deleted_folder(mailfolder, recursive)
 
         if to_mailfolder is not None:
             target_mbox = self.parse_mailfolder(to_mailfolder)
@@ -603,20 +603,26 @@
 
         return mbox
 
-    def _find_deleted_folder(self, mbox):
+    def _find_deleted_folder(self, mbox, recursive=True):
         """
             Give me the parts that are in an original mailfolder name and I'll
             find the deleted folder name.
 
             TODO: It finds virtdomain folders for non-virtdomain searches.
         """
-        deleted_folder_search = "%(deleted_prefix)s%(separator)s%(mailfolder)s%(separator)s*" % {
+        deleted_folder_search = "%(deleted_prefix)s%(separator)s%(mailfolder)s" % {
                 # TODO: The prefix used is configurable
                 'deleted_prefix': "DELETED",
                 'mailfolder': self.separator.join(mbox['path_parts']),
                 'separator': self.separator,
             }
 
+        if recursive:
+            deleted_folder_search = "%s%s*" % (
+                    deleted_folder_search,
+                    self.separator
+                )
+
         if mbox['domain'] is not None:
             deleted_folder_search = "%s@%s" % (
                     deleted_folder_search,