diff --git a/lib/tunnelbroker/peer-to-peer-context.js b/lib/tunnelbroker/peer-to-peer-context.js
--- a/lib/tunnelbroker/peer-to-peer-context.js
+++ b/lib/tunnelbroker/peer-to-peer-context.js
@@ -10,6 +10,7 @@
 } from './tunnelbroker-context.js';
 import { usePeerOlmSessionsCreatorContext } from '../components/peer-olm-session-creator-provider.react.js';
 import { useSendPushNotifs } from '../push/send-hooks.react.js';
+import { getAllPeerDevices } from '../selectors/user-selectors.js';
 import {
   type AuthMetadata,
   IdentityClientContext,
@@ -26,6 +27,7 @@
   handleOutboundP2PMessage,
   type HandleOutboundP2PMessageResult,
 } from '../utils/peer-to-peer-communication-utils.js';
+import { useSelector } from '../utils/redux-utils.js';
 
 type PeerToPeerContextType = {
   +processOutboundMessages: (
@@ -113,6 +115,7 @@
     devices: $ReadOnlyArray<DeviceSessionCreationRequest>,
   ) => Promise<void>,
   messageIDs: ?$ReadOnlyArray<string>,
+  allPeerDevices: Set<string>,
 ): Promise<ProcessOutboundP2PMessagesResult> {
   let authMetadata;
   try {
@@ -166,9 +169,27 @@
   const messagesPromises: Array<Promise<HandleOutboundP2PMessageResult>> = [];
   for (const message: OutboundP2PMessage of messages) {
     messagesMap[message.messageID] = message;
-    messagesPromises.push(
-      handleOutboundP2PMessage(message, authMetadata, sendMessage),
-    );
+
+    // If the message was addressed to a peer that no longer
+    // exists we can remove it and return success.
+    if (!allPeerDevices.has(message.deviceID)) {
+      messagesPromises.push(
+        (async () => {
+          await sqliteAPI.removeOutboundP2PMessage(
+            message.messageID,
+            message.deviceID,
+          );
+          return {
+            status: 'success',
+            messageID: message.messageID,
+          };
+        })(),
+      );
+    } else {
+      messagesPromises.push(
+        handleOutboundP2PMessage(message, authMetadata, sendMessage),
+      );
+    }
   }
   const messagesResults: Array<HandleOutboundP2PMessageResult> =
     await Promise.all(messagesPromises);
@@ -253,6 +274,7 @@
       +outboundMessageIDs: ?$ReadOnlyArray<string>,
       +dmOpID: ?string,
       +notificationsCreationData: ?NotificationsCreationData,
+      +allPeerDevices: Set<string>,
     }>,
   >([]);
   const promiseRunning = React.useRef<boolean>(false);
@@ -260,6 +282,11 @@
   const { createOlmSessionsWithUser: peerOlmSessionsCreator } =
     usePeerOlmSessionsCreatorContext();
   const sendPushNotifs = useSendPushNotifs();
+  const allPeerDevices = useSelector(getAllPeerDevices);
+  const allPeerDevicesSet = React.useMemo(
+    () => new Set<string>(allPeerDevices),
+    [allPeerDevices],
+  );
 
   const processOutboundMessages = React.useCallback(
     (
@@ -271,6 +298,7 @@
         outboundMessageIDs,
         dmOpID,
         notificationsCreationData,
+        allPeerDevices: allPeerDevicesSet,
       });
       if (!promiseRunning.current) {
         promiseRunning.current = true;
@@ -284,6 +312,7 @@
                   identityContext,
                   peerOlmSessionsCreator,
                   queueFront?.outboundMessageIDs,
+                  queueFront.allPeerDevices,
                 ),
                 sendPushNotifs(queueFront.notificationsCreationData),
               ]);
@@ -314,10 +343,11 @@
       }
     },
     [
-      sendPushNotifs,
-      peerOlmSessionsCreator,
-      identityContext,
+      allPeerDevicesSet,
       sendMessageToDevice,
+      identityContext,
+      peerOlmSessionsCreator,
+      sendPushNotifs,
     ],
   );