diff --git a/lib/shared/message-utils.js b/lib/shared/message-utils.js
--- a/lib/shared/message-utils.js
+++ b/lib/shared/message-utils.js
@@ -118,52 +118,34 @@
   });
 }
 
-type LengthResult = {
-  +local: number,
-  +realized: number,
-};
-function findMessageIDMaxLengths(
-  messageIDs: $ReadOnlyArray<?string>,
-): LengthResult {
-  const result = {
-    local: 0,
-    realized: 0,
-  };
+function findMessageIDMaxLength(messageIDs: $ReadOnlyArray<?string>): number {
+  let result = 0;
   for (const id of messageIDs) {
-    if (!id) {
+    if (!id || id.startsWith(localIDPrefix)) {
       continue;
     }
-    if (id.startsWith(localIDPrefix)) {
-      result.local = Math.max(result.local, id.length - localIDPrefix.length);
-    } else {
-      result.realized = Math.max(result.realized, id.length);
-    }
+
+    result = Math.max(result, id.length);
   }
   return result;
 }
 
-function extendMessageID(id: ?string, lengths: LengthResult): ?string {
-  if (!id) {
+function extendMessageID(id: ?string, length: number): ?string {
+  if (!id || id.startsWith(localIDPrefix)) {
     return id;
   }
-  if (id.startsWith(localIDPrefix)) {
-    const zeroPaddedID = id
-      .substr(localIDPrefix.length)
-      .padStart(lengths.local, '0');
-    return `${localIDPrefix}${zeroPaddedID}`;
-  }
-  return id.padStart(lengths.realized, '0');
+  return id.padStart(length, '0');
 }
 
 function sortMessageInfoList<T: MessageInfo | RawMessageInfo>(
   messageInfos: $ReadOnlyArray<T>,
 ): T[] {
-  const lengths = findMessageIDMaxLengths(
-    messageInfos.map(message => message?.id ?? message?.localID),
+  const length = findMessageIDMaxLength(
+    messageInfos.map(message => message?.id),
   );
   return _orderBy([
     'time',
-    (message: T) => extendMessageID(message?.id ?? message?.localID, lengths),
+    (message: T) => extendMessageID(message?.id ?? message?.localID, length),
   ])(['desc', 'desc'])(messageInfos);
 }
 
@@ -171,10 +153,10 @@
   +[id: string]: RawMessageInfo,
 }) => (messageIDs: $ReadOnlyArray<string>) => string[] =
   messages => messageIDs => {
-    const lengths = findMessageIDMaxLengths(messageIDs);
+    const length = findMessageIDMaxLength(messageIDs);
     return _orderBy([
       (id: string) => messages[id].time,
-      (id: string) => extendMessageID(id, lengths),
+      (id: string) => extendMessageID(id, length),
     ])(['desc', 'desc'])(messageIDs);
   };
 
diff --git a/lib/shared/message-utils.test.js b/lib/shared/message-utils.test.js
--- a/lib/shared/message-utils.test.js
+++ b/lib/shared/message-utils.test.js
@@ -804,67 +804,71 @@
 });
 
 describe('sortMessageInfoList', () => {
-  it('should sort messages by time and then by the number in id', () => {
-    const messages: $ReadOnlyArray<RawMessageInfo> = [
-      {
-        type: 0,
-        threadID: '256|100',
-        creatorID: '256',
-        time: 4,
-        text: 'test',
-        id: '256|9',
-      },
-      {
-        type: 0,
-        threadID: '256|100',
-        creatorID: '256',
-        time: 2,
-        text: 'test',
-        localID: 'local100',
-      },
-      {
-        type: 0,
-        threadID: '256|100',
-        creatorID: '256',
-        time: 1,
-        text: 'test',
-        id: '256|1',
-      },
-      {
-        type: 0,
-        threadID: '256|100',
-        creatorID: '256',
-        time: 1,
-        text: 'test',
-        localID: 'local10',
-      },
-      {
-        type: 0,
-        threadID: '256|100',
-        creatorID: '256',
-        time: 1,
-        text: 'test',
-        localID: 'local200',
-      },
-      {
-        type: 0,
-        threadID: '256|100',
-        creatorID: '256',
-        time: 1,
-        text: 'test',
-        id: '256|20',
-      },
-    ];
-    const result = sortMessageInfoList(messages);
-    expect(result.map(item => item.id ?? item.localID)).toEqual([
-      '256|9',
-      'local100',
-      'local200',
-      'local10',
-      '256|20',
-      '256|1',
-    ]);
-  });
+  it(
+    'should sort messages by time and then by the number in id. ' +
+      'Local ids should be sorted lexicographically',
+    () => {
+      const messages: $ReadOnlyArray<RawMessageInfo> = [
+        {
+          type: 0,
+          threadID: '256|100',
+          creatorID: '256',
+          time: 4,
+          text: 'test',
+          id: '256|9',
+        },
+        {
+          type: 0,
+          threadID: '256|100',
+          creatorID: '256',
+          time: 2,
+          text: 'test',
+          localID: 'local100',
+        },
+        {
+          type: 0,
+          threadID: '256|100',
+          creatorID: '256',
+          time: 1,
+          text: 'test',
+          id: '256|1',
+        },
+        {
+          type: 0,
+          threadID: '256|100',
+          creatorID: '256',
+          time: 1,
+          text: 'test',
+          localID: 'local20',
+        },
+        {
+          type: 0,
+          threadID: '256|100',
+          creatorID: '256',
+          time: 1,
+          text: 'test',
+          localID: 'local100',
+        },
+        {
+          type: 0,
+          threadID: '256|100',
+          creatorID: '256',
+          time: 1,
+          text: 'test',
+          id: '256|20',
+        },
+      ];
+      const result = sortMessageInfoList(messages);
+      expect(result.map(item => item.id ?? item.localID)).toEqual([
+        '256|9',
+        'local100',
+        'local20',
+        'local100',
+        '256|20',
+        '256|1',
+      ]);
+    },
+  );
 
   it('on the keyserver, should sort messages by time and then by id', () => {
     const messages: $ReadOnlyArray<RawMessageInfo> = [
@@ -930,9 +934,67 @@
 });
 
 describe('sortMessageIDs', () => {
-  it('should sort messages by time and then by the number in id', () => {
+  it(
+    'should sort messages by time and then by the number in id. ' +
+      'Local ids should be sorted lexicographically',
+    () => {
+      const messages = {
+        ['256|0']: {
+          type: 0,
+          threadID: '100',
+          creatorID: '256',
+          time: 5,
+          text: 'test',
+          id: '256|0',
+        },
+        ['256|100']: {
+          type: 0,
+          threadID: '100',
+          creatorID: '256',
+          time: 1,
+          text: 'test',
+          id: '256|100',
+        },
+        ['local333']: {
+          type: 0,
+          threadID: '100',
+          creatorID: '256',
+          time: 1,
+          text: 'test',
+          localID: 'local333',
+        },
+        ['256|1325993']: {
+          type: 0,
+          threadID: '100',
+          creatorID: '256',
+          time: 1,
+          text: 'test',
+          localID: '256|1325993',
+        },
+        ['256|1']: {
+          type: 0,
+          threadID: '100',
+          creatorID: '256',
+          time: 1,
+          text: 'test',
+          id: '256|1',
+        },
+      };
+      expect(
+        sortMessageIDs(messages)([
+          '256|0',
+          '256|100',
+          'local333',
+          '256|1325993',
+          '256|1',
+        ]),
+      ).toEqual(['256|0', 'local333', '256|1325993', '256|100', '256|1']);
+    },
+  );
+
+  it('should sort local ids lexicographically', () => {
     const messages = {
-      ['256|0']: {
+      ['local9']: {
         type: 0,
         threadID: '100',
         creatorID: '256',
@@ -940,7 +1002,7 @@
         text: 'test',
         id: '256|0',
       },
-      ['256|100']: {
+      ['local100']: {
         type: 0,
         threadID: '100',
         creatorID: '256',
@@ -956,31 +1018,9 @@
         text: 'test',
         localID: 'local333',
       },
-      ['256|1325993']: {
-        type: 0,
-        threadID: '100',
-        creatorID: '256',
-        time: 1,
-        text: 'test',
-        localID: '256|1325993',
-      },
-      ['256|1']: {
-        type: 0,
-        threadID: '100',
-        creatorID: '256',
-        time: 1,
-        text: 'test',
-        id: '256|1',
-      },
     };
     expect(
-      sortMessageIDs(messages)([
-        '256|0',
-        '256|100',
-        'local333',
-        '256|1325993',
-        '256|1',
-      ]),
-    ).toEqual(['256|0', 'local333', '256|1325993', '256|100', '256|1']);
+      sortMessageIDs(messages)(['local9', 'local100', 'local333']),
+    ).toEqual(['local9', 'local333', 'local100']);
   });
 });