Index: kdepim/kmail/cachedimapjob.cpp
===================================================================
--- kdepim/kmail/cachedimapjob.cpp	(revision 1022967)
+++ kdepim/kmail/cachedimapjob.cpp	(revision 1022968)
@@ -510,7 +510,7 @@
         bool b = kmkernel->iCalIface().isResourceQuiet();
         kmkernel->iCalIface().setResourceQuiet( true );
 
-        mFolder->take( i );
+        mFolder->takeTemporarily( i );
         mFolder->addMsgKeepUID( mMsg );
         mMsg->setTransferInProgress( false );
 
Index: kdepim/kmail/kmfoldercachedimap.cpp
===================================================================
--- kdepim/kmail/kmfoldercachedimap.cpp	(revision 1022967)
+++ kdepim/kmail/kmfoldercachedimap.cpp	(revision 1022968)
@@ -520,6 +520,11 @@
   return KMFolderMaildir::take( idx );
 }
 
+void KMFolderCachedImap::takeTemporarily( int idx )
+{
+  KMFolderMaildir::take( idx );
+}
+
 int KMFolderCachedImap::addMsgInternal( KMMessage *msg, bool newMail, int *index_return )
 {
   // Possible optimization: Only dirty if not filtered below
Index: kdepim/kmail/kmfoldercachedimap.h
===================================================================
--- kdepim/kmail/kmfoldercachedimap.h	(revision 1022967)
+++ kdepim/kmail/kmfoldercachedimap.h	(revision 1022968)
@@ -228,10 +228,23 @@
     /** Reimplemented from KMFolder. Moving is not supported, so aParent must be 0. */
     virtual int rename( const QString &aName, KMFolderDir *aParent = 0 );
 
-    /** Reimplemented from KMFolderMaildir */
-    virtual KMMessage *take( int idx );
     bool canDeleteMessages() const;
 
+    /**
+     * Reimplemented from KMFolderMaildir
+     * This deletes the message permanently, also from the server. For this,
+     * rememberDeletion() is called, so that the message can be deleted from
+     * the server on the next sync.
+     */
+    virtual KMMessage* take( int idx );
+
+    /**
+     * Like take(), only that the deletion is not remembered, i.e. the
+     * message will not be deleted from the server. Calling this can cause
+     * inconsistencies, so make sure you re-add the message later!
+     */
+    void takeTemporarily( int idx );
+
     /** Reimplemented from KMFolderMaildir */
     virtual int addMsg( KMMessage *msg, int *index_return = 0 );
 
Index: kdepim/kmail/kmfoldercachedimap.cpp
===================================================================
--- kdepim/kmail/kmfoldercachedimap.cpp	(revision 1022977)
+++ kdepim/kmail/kmfoldercachedimap.cpp	(revision 1022978)
@@ -1662,6 +1662,11 @@
     job->start();
     return true;
   } else {
+
+    // Nothing to delete on the server, make sure the map is clear again.
+    // Normally this wouldn't be necessary, but there can be stale maps because of
+    // https://issues.kolab.org/issue3833.
+    mDeletedUIDsSinceLastSync.clear();
     return false;
   }
 }