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
@@ -367,8 +367,7 @@
   );
   const orderedNewMessageInfos = _flow(
     _map((messageInfo: RawMessageInfo) => {
-      const { id: inputID } = messageInfo;
-      invariant(inputID, 'new messageInfos should have serverID');
+      const inputID = messageID(messageInfo);
       invariant(
         !threadIsPending(messageInfo.threadID),
         'new messageInfos should have realized thread id',
@@ -428,10 +427,15 @@
               localID: currentLocalMessageInfo.localID,
             }: RawImagesMessageInfo);
           }
-        } else {
-          // If neither the serverID nor the localID from the delivered
-          // RawMessageInfo exists in the client store, then this message is
-          // brand new to us. Ignore any localID provided by the server.
+        } else if (messageInfo.id) {
+          // For keyserver messages, if neither the serverID nor the localID
+          // from the delivered RawMessageInfo exists in the client store, then
+          // this message is brand new to us. Ignore any localID provided by
+          // the server.
+          // Failed messages that don't use a keyserver protocol have
+          // localID and don't have an ID yet. We shouldn't remove their
+          // localID to avoid a situation when a message doesn't have any
+          // type of ID.
           // (The conditional below is for Flow)
           const { localID, ...rest } = messageInfo;
           if (rest.type === messageTypes.TEXT) {