diff --git a/camel/camel-folder-summary.c b/camel/camel-folder-summary.c
index c2e6d55..d9ee120 100644
--- a/camel/camel-folder-summary.c
+++ b/camel/camel-folder-summary.c
@@ -2121,6 +2122,9 @@ camel_folder_summary_clear(CamelFolderSummary *s)
 		return;
 	}
 	
+	g_hash_table_destroy (s->priv->flag_cache);
+	s->priv->flag_cache = g_hash_table_new (g_str_hash, g_str_equal);
+
 	g_ptr_array_foreach (s->uids, (GFunc) camel_pstring_free, NULL);
 	g_ptr_array_free (s->uids, TRUE);
 	s->uids = g_ptr_array_new ();
@@ -2153,7 +2157,10 @@ camel_folder_summary_clear_db (CamelFolderSummary *s)
 		CAMEL_SUMMARY_UNLOCK(s, summary_lock);
 		return;
 	}
-	
+
+	g_hash_table_destroy (s->priv->flag_cache);
+	s->priv->flag_cache = g_hash_table_new (g_str_hash, g_str_equal);
+
 	g_ptr_array_foreach (s->uids, (GFunc) camel_pstring_free, NULL);
 	g_ptr_array_free (s->uids, TRUE);
 	s->uids = g_ptr_array_new ();
@@ -2181,6 +2188,7 @@ summary_remove_uid (CamelFolderSummary *s, const char *uid)
 	for (i=0; i<s->uids->len; i++) {
 		if (strcmp(s->uids->pdata[i], uid) == 0) {
 			/* FIXME: Does using fast remove affect anything ? */
+			g_hash_table_remove (s->priv->flag_cache, uid);
 			g_ptr_array_remove_index(s->uids, i);
 			camel_pstring_free (uid);
 			return 0;
@@ -2302,6 +2310,7 @@ camel_folder_summary_remove_index_fast (CamelFolderSummary *s, int index)
 	if (g_hash_table_lookup_extended(s->loaded_infos, uid, (void *)&olduid, (void *)&oldinfo)) {
 		/* make sure it doesn't vanish while we're removing it */
 		g_hash_table_remove (s->loaded_infos, uid);
+		g_hash_table_remove (s->priv->flag_cache, uid);
 		camel_pstring_free (uid);
 		g_ptr_array_remove_index(s->uids, index);
 		CAMEL_SUMMARY_UNLOCK(s, ref_lock);
@@ -2310,6 +2319,7 @@ camel_folder_summary_remove_index_fast (CamelFolderSummary *s, int index)
 	} else {
 		/* Info isn't loaded into the memory. We must just remove the UID*/
 		g_ptr_array_remove_index(s->uids, index);
+		g_hash_table_remove (s->priv->flag_cache, uid);	
 		camel_pstring_free (uid);
 		CAMEL_SUMMARY_UNLOCK(s, ref_lock);
 		CAMEL_SUMMARY_UNLOCK(s, summary_lock);
@@ -2369,6 +2379,7 @@ camel_folder_summary_remove_range (CamelFolderSummary *s, int start, int end)
 			uids = g_slist_prepend (uids, (gpointer) uid);
 
 			if (g_hash_table_lookup_extended (s->loaded_infos, uid, &olduid, &oldinfo)) {
+				g_hash_table_remove (s->priv->flag_cache, uid);
 				camel_message_info_free (oldinfo);
 				g_hash_table_remove (s->loaded_infos, uid);
 			}
