diff --git a/lib/reducers/message-reducer.js b/lib/reducers/message-reducer.js
--- a/lib/reducers/message-reducer.js
+++ b/lib/reducers/message-reducer.js
@@ -179,10 +179,6 @@
       payload: { id: messageID(messageInfo), messageInfo },
     }),
   );
-  const messageStoreOperations = [
-    { type: 'remove_all' },
-    ...messageStoreReplaceOperations,
-  ];
 
   const threadsToMessageIDs =
     mapThreadsToMessageIDsFromOrderedMessageInfos(orderedMessageInfos);
@@ -205,6 +201,19 @@
     }
     threads[threadID] = newThread();
   }
+
+  const messageStoreOperations = [
+    { type: 'remove_all' },
+    ...messageStoreReplaceOperations,
+    {
+      type: 'remove_all_threads',
+    },
+    {
+      type: 'replace_threads',
+      payload: { threads },
+    },
+  ];
+
   return {
     messageStoreOperations,
     messageStore: { messages, threads, local: {}, currentAsOf },
@@ -805,6 +814,12 @@
       messageStoreOperations,
     );
 
+    assertMessageStoreThreadsAreEqual(
+      processedMessageStore,
+      freshStore,
+      `${action.type} | fresh store`,
+    );
+
     return {
       messageStoreOperations,
       messageStore: { ...freshStore, messages: processedMessageStore.messages },