diff --git a/lib/reducers/user-reducer.js b/lib/reducers/user-reducer.js
--- a/lib/reducers/user-reducer.js
+++ b/lib/reducers/user-reducer.js
@@ -36,6 +36,7 @@
 } from '../types/socket-types.js';
 import { updateTypes } from '../types/update-types-enum.js';
 import { processUpdatesActionType } from '../types/update-types.js';
+import type { ClientUpdateInfo } from '../types/update-types.js';
 import type {
   CurrentUserInfo,
   UserInfos,
@@ -158,6 +159,24 @@
 
 const { processStoreOperations: processUserStoreOps } = userStoreOpsHandlers;
 
+function generateOpsForUserUpdates(
+  userInfos: UserInfos,
+  payload: {
+    +updatesResult: { +newUpdates: $ReadOnlyArray<ClientUpdateInfo>, ... },
+    ...
+  },
+): $ReadOnlyArray<UserStoreOperation> {
+  return payload.updatesResult.newUpdates
+    .map(update =>
+      updateSpecs[update.type].generateOpsForUserInfoUpdates?.(
+        userInfos,
+        update,
+      ),
+    )
+    .filter(Boolean)
+    .flat();
+}
+
 function reduceUserInfos(
   state: UserStore,
   action: BaseAction,
@@ -241,6 +260,10 @@
     const newUserInfos = _keyBy(userInfo => userInfo.id)(
       action.payload.userInfos,
     );
+    const userStoreOps: UserStoreOperation[] = [
+      ...convertUserInfosToReplaceUserOps(newUserInfos),
+      ...generateOpsForUserUpdates(state.userInfos, action.payload),
+    ];
     const updated = action.payload.updatesResult.newUpdates.reduce(
       (reducedState, update) => {
         const { reduceUserInfos: reduceUserInfosUpdate } =
@@ -251,6 +274,17 @@
       },
       { ...state.userInfos, ...newUserInfos },
     );
+
+    const processedUserInfos: UserInfos = processUserStoreOps(
+      state.userInfos,
+      userStoreOps,
+    );
+    assertUserStoresAreEqual(
+      processedUserInfos,
+      updated,
+      action.type,
+      onStateDifference,
+    );
     if (!_isEqual(state.userInfos)(updated)) {
       return [
         {
diff --git a/lib/shared/updates/delete-account-spec.js b/lib/shared/updates/delete-account-spec.js
--- a/lib/shared/updates/delete-account-spec.js
+++ b/lib/shared/updates/delete-account-spec.js
@@ -74,4 +74,15 @@
     updateTypes.UPDATE_USER,
   ]),
   typesOfReplacedUpdatesForMatchingKey: 'all_types',
+  generateOpsForUserInfoUpdates(
+    state: UserInfos,
+    update: AccountDeletionUpdateInfo,
+  ) {
+    const { deletedUserID } = update;
+    if (!state[deletedUserID]) {
+      return [];
+    }
+
+    return [{ type: 'remove_users', payload: { ids: [update.deletedUserID] } }];
+  },
 });
diff --git a/lib/shared/updates/update-spec.js b/lib/shared/updates/update-spec.js
--- a/lib/shared/updates/update-spec.js
+++ b/lib/shared/updates/update-spec.js
@@ -1,6 +1,7 @@
 // @flow
 
 import type { ThreadStoreOperation } from '../../ops/thread-store-ops.js';
+import type { UserStoreOperation } from '../../ops/user-store-ops.js';
 import type {
   FetchEntryInfosBase,
   RawEntryInfo,
@@ -90,4 +91,8 @@
   ) => ?UpdateInfo,
   +deleteCondition: ?UpdateTypes,
   +typesOfReplacedUpdatesForMatchingKey: ?UpdateTypes,
+  +generateOpsForUserInfoUpdates?: (
+    state: UserInfos,
+    update: UpdateInfo,
+  ) => ?$ReadOnlyArray<UserStoreOperation>,
 };