diff --git a/pykolab/imap/cyrus.py b/pykolab/imap/cyrus.py
--- a/pykolab/imap/cyrus.py
+++ b/pykolab/imap/cyrus.py
@@ -470,7 +470,11 @@
             target_server = self.find_mailfolder_server(target_folder)
 
             if hasattr(conf, 'dry_run') and not conf.dry_run:
-                if target_server is not self.server:
+                source_server = self.find_mailfolder_server(undelete_folder)
+                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)
@@ -589,7 +593,7 @@
                     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.
         #
@@ -606,4 +610,4 @@
 
             folders = _folders
 
-        return folders
+        return [self.folder_utf8(x) for x in folders]