--- src/lib-storage/index/maildir/maildir-storage.c.orig        2010-04-17 13:17:10.000000000 +0400
+++ src/lib-storage/index/maildir/maildir-storage.c     2010-04-17 13:17:19.000000000 +0400
@@ -5,6 +5,9 @@
 #include "array.h"
 #include "hostpid.h"
 #include "str.h"
+#include "hex-binary.h"
+#include "hostpid.h"
+#include "randgen.h"
 #include "mkdir-parents.h"
 #include "eacces-error.h"
 #include "unlink-directory.h"
@@ -59,6 +62,16 @@
                                enum mailbox_list_file_type type,
                                enum mailbox_info_flags *flags_r);

+static const char *unique_fname(void)
+{
+       unsigned char randbuf[8];
+
+       random_fill_weak(randbuf, sizeof(randbuf));
+       return t_strdup_printf("%s.%s.%s", my_hostname, my_pid,
+                              binary_to_hex(randbuf, sizeof(randbuf)));
+
+}
+
 static int
 maildir_get_list_settings(struct mailbox_list_settings *list_set,
                          const char *data, struct mail_storage *storage,
@@ -770,7 +783,7 @@
 {
        struct maildir_storage *storage = MAILDIR_LIST_CONTEXT(list);
        struct stat st;
-       const char *src, *dest, *base;
+       const char *src, *dest, *base, *trash_dest;
        int count;

        /* Make sure the indexes are closed before trying to delete the
@@ -825,29 +838,48 @@
           marks it as being deleted. If we die before deleting the
           ..DOVECOT-TRASH directory, it gets deleted the next time
           mailbox listing sees it. */
-       count = 0;
-       while (rename(src, dest) < 0) {
+       count = 0; trash_dest = dest;
+       for (; rename(src, trash_dest) < 0; count++) {
                if (errno == ENOENT) {
                        /* it was just deleted under us by
                           another process */
+                       if (trash_dest != dest && count < 5) {
+                               /* either the source was just deleted or
+                                  the trash dir was deleted. */
+                               trash_dest = dest;
+                               continue;
+                       }
                        mailbox_list_set_error(list, MAIL_ERROR_NOTFOUND,
                                T_MAIL_ERR_MAILBOX_NOT_FOUND(name));
                        return -1;
                }
                if (!EDESTDIREXISTS(errno)) {
                        mailbox_list_set_critical(list,
-                               "rename(%s, %s) failed: %m", src, dest);
+                               "rename(%s, %s) failed: %m", src, trash_dest);
                        return -1;
                }

                /* already existed, delete it and try again */
-               if (unlink_directory(dest, TRUE) < 0 &&
-                   (errno != ENOTEMPTY || count >= 5)) {
+                               /* trash dir already exists. the reasons for this are:
+
+                  a) another process is in the middle of deleting it
+                  b) previous process crashed and didn't delete it
+                  c) NFS: mailbox was recently deleted, but some connection
+                     still has that mailbox open. the directory contains .nfs*
+                     files that can't be deleted until the mailbox is closed.
+
+                  Because of c) we'll first try to rename the mailbox under
+                  the trash directory and only later try to delete the entire
+                  trash directory. */
+               if (dest == trash_dest) {
+                       trash_dest = t_strconcat(dest, "/",
+                                                unique_fname(), NULL);
+               } else if (unlink_directory(trash_dest, TRUE) < 0 &&
+                          (errno != ENOTEMPTY || count >= 5)) {
                        mailbox_list_set_critical(list,
-                               "unlink_directory(%s) failed: %m", dest);
+                               "unlink_directory(%s) failed: %m", trash_dest);
                        return -1;
                }
-               count++;
        }

        if (unlink_directory(dest, TRUE) < 0 && errno != ENOTEMPTY) {