diff --git a/pykolab/imap/cyrus.py b/pykolab/imap/cyrus.py
--- a/pykolab/imap/cyrus.py
+++ b/pykolab/imap/cyrus.py
@@ -340,17 +340,30 @@
             log.info(_("Undeleting %s to %s") % (undelete_folder,target_folder))
 
             target_server = self.find_mailfolder_server(target_folder)
+            source_server = self.find_mailfolder_server(undelete_folder)
 
-            if hasattr(conf,'dry_run') and not conf.dry_run:
-                if not target_server == self.server:
-                    self.xfer(undelete_folder,target_server)
+            if hasattr(conf, 'dry_run') and not conf.dry_run:
+                undelete_folder = self.folder_utf7(undelete_folder)
+                target_folder = self.folder_utf7(target_folder)
+
+                if not target_server == source_server:
+                    self.xfer(undelete_folder, target_server)
 
                 self.rename(undelete_folder,target_folder)
             else:
-                if not target_server == self.server:
-                    print >> sys.stdout, _("Would have transferred %s from %s to %s") % (undelete_folder, self.server, target_server)
-
-                print >> sys.stdout, _("Would have renamed %s to %s") % (undelete_folder, target_folder)
+                if not target_server == source_server:
+                    print >> sys.stdout, \
+                        _("Would have transferred %s from %s to %s") % (
+                                undelete_folder,
+                                source_server,
+                                target_server
+                            )
+
+                print >> sys.stdout, \
+                    _("Would have renamed %s to %s") % (
+                            undelete_folder,
+                            target_folder
+                        )
 
     def parse_mailfolder(self, mailfolder):
         """
@@ -441,7 +454,7 @@
         if not mbox['domain'] == None:
             deleted_folder_search = "%s@%s" % (deleted_folder_search,mbox['domain'])
 
-        folders = self.lm(deleted_folder_search)
+        folders = self.lm(self.folder_utf7(deleted_folder_search))
 
         # The folders we have found at this stage include virtdomain folders.
         #
@@ -458,4 +471,4 @@
 
             folders = _folders
 
-        return folders
+        return [self.folder_utf8(x) for x in folders]