diff --git a/keyserver/src/database/search-utils.js b/keyserver/src/database/search-utils.js
--- a/keyserver/src/database/search-utils.js
+++ b/keyserver/src/database/search-utils.js
@@ -39,8 +39,14 @@
   messages: $ReadOnlyArray<RawMessageInfo | ProcessedForSearchRow>,
 ): Promise<void> {
   const processedMessages = [];
+  const deletedMessages = new Set<string>();
 
   for (const msg of messages) {
+    if (msg.type === messageTypes.DELETE_MESSAGE) {
+      deletedMessages.add(msg.targetMessageID);
+      continue;
+    }
+
     if (
       msg.type !== messageTypes.TEXT &&
       msg.type !== messageTypes.EDIT_MESSAGE
@@ -57,17 +63,37 @@
     }
   }
 
-  if (processedMessages.length === 0) {
-    return;
+  const messagesToInsert = processedMessages.filter(
+    ([messageID]) => messageID && !deletedMessages.has(messageID),
+  );
+  const messagesToDelete = [...deletedMessages];
+
+  const queries = [];
+
+  if (messagesToInsert.length > 0) {
+    queries.push(
+      dbQuery(SQL`
+        INSERT INTO message_search (original_message_id, message_id, 
+          processed_content)
+        VALUES ${messagesToInsert}
+        ON DUPLICATE KEY UPDATE
+          message_id = VALUE(message_id),
+          processed_content = VALUE(processed_content);
+      `),
+    );
+  }
+
+  if (messagesToDelete.length > 0) {
+    queries.push(
+      dbQuery(SQL`
+        DELETE
+        FROM message_search
+        WHERE original_message_id IN (${messagesToDelete})
+      `),
+    );
   }
 
-  await dbQuery(SQL`
-    INSERT INTO message_search (original_message_id, message_id, processed_content)
-    VALUES ${processedMessages}
-    ON DUPLICATE KEY UPDATE
-      message_id = VALUE(message_id),
-      processed_content = VALUE(processed_content);
-  `);
+  await Promise.all(queries);
 }
 
 type ProcessedForSearchRowText = {
diff --git a/keyserver/src/fetchers/message-fetchers.js b/keyserver/src/fetchers/message-fetchers.js
--- a/keyserver/src/fetchers/message-fetchers.js
+++ b/keyserver/src/fetchers/message-fetchers.js
@@ -856,6 +856,7 @@
         m.type = ${messageTypes.SIDEBAR_SOURCE}
         OR m.type = ${messageTypes.REACTION}
         OR m.type = ${messageTypes.TOGGLE_PIN}
+        OR m.type = ${messageTypes.DELETE_MESSAGE}
       )
     UNION SELECT m.id, m.thread AS threadID, m.content, m.time, m.type, 
       m.creation, m.user AS creatorID, m.target_message as targetMessageID,