--- a/toolkit/components/places/SyncedBookmarksMirror.jsm
+++ b/toolkit/components/places/SyncedBookmarksMirror.jsm
@@ -1059,50 +1059,49 @@ class SyncedBookmarksMirror {
                                  guid, parentGuid, level)
         SELECT b.id, b.parent, b.position, b.type, b.fk, b.guid, p.guid,
                o.level
         FROM moz_bookmarks b
         JOIN moz_bookmarks p ON p.id = b.parent
         JOIN guidsWithLevelsToDelete o ON o.guid = b.guid`,
         guids);
 
-      let guidsParams = new Array(guids.length).fill("?").join(",");
-
-      // Recalculate frecencies.
+      // Recalculate frecencies. The `isUntagging` check is a formality, since
+      // tags shouldn't have annos or tombstones, should not appear in local
+      // deletions, and should not affect frecency. This can go away with
+      // bug 1293445.
       await this.db.execute(`
         UPDATE moz_places SET
           frecency = -1
-        WHERE id IN (SELECT fk FROM moz_bookmarks
-                     WHERE guid IN (${guidsParams}))`,
-        guids);
+        WHERE id IN (SELECT placeId FROM itemsRemoved
+                     WHERE NOT isUntagging)`);
 
       // Remove annos for the deleted items.
       await this.db.execute(`
         DELETE FROM moz_items_annos
-        WHERE item_id = (SELECT id FROM moz_bookmarks
-                         WHERE guid IN (${guidsParams}))`,
-        guids);
+        WHERE item_id IN (SELECT itemId FROM itemsRemoved
+                          WHERE NOT isUntagging)`);
 
       // Remove any local tombstones for deleted items.
       await this.db.execute(`
         DELETE FROM moz_bookmarks_deleted
-        WHERE guid IN (${guidsParams})`,
-        guids);
+        WHERE guid IN (SELECT guid FROM itemsRemoved)`);
 
       await this.db.execute(`
-        DELETE FROM moz_bookmarks WHERE guid IN (${guidsParams})`,
-        guids);
+        DELETE FROM moz_bookmarks
+        WHERE id IN (SELECT itemId FROM itemsRemoved
+                     WHERE NOT isUntagging)`);
 
       // Flag locally deleted items as merged.
       await this.db.execute(`
         UPDATE items SET
           needsMerge = 0
         WHERE needsMerge AND
-              guid IN (${guidsParams})`,
-        guids);
+              guid IN (SELECT guid FROM itemsRemoved
+                       WHERE NOT isUntagging)`);
     }
 
     MirrorLog.debug("Flagging remotely deleted items as merged");
     for (let chunk of PlacesSyncUtils.chunkArray(remoteDeletions,
       SQLITE_MAX_VARIABLE_NUMBER)) {
 
       await this.db.execute(`
         UPDATE items SET
@@ -3068,29 +3067,48 @@ class BookmarkMerger {
     this.telemetryEvents = [];
   }
 
   merge() {
     let localRoot = this.localTree.nodeForGuid(PlacesUtils.bookmarks.rootGuid);
     let remoteRoot = this.remoteTree.nodeForGuid(PlacesUtils.bookmarks.rootGuid);
     let mergedRoot = this.mergeNode(PlacesUtils.bookmarks.rootGuid, localRoot,
                                     remoteRoot);
+
+    // Any remaining deletions on one side should be deleted on the other side.
+    // This happens when the remote tree has tombstones for items that don't
+    // exist in Places, or Places has tombstones for items that aren't on the
+    // server.
+    for (let guid of this.localTree.deletedGuids) {
+      if (!this.mentions(guid)) {
+        this.deleteRemotely.add(guid);
+      }
+    }
+    for (let guid of this.remoteTree.deletedGuids) {
+      if (!this.mentions(guid)) {
+        this.deleteLocally.add(guid);
+      }
+    }
     return mergedRoot;
   }
 
   subsumes(tree) {
     for (let guid of tree.guids()) {
-      if (!this.mergedGuids.has(guid) && !this.deleteLocally.has(guid) &&
-          !this.deleteRemotely.has(guid)) {
+      if (!this.mentions(guid)) {
         return false;
       }
     }
     return true;
   }
 
+  mentions(guid) {
+    return this.mergedGuids.has(guid) || this.deleteLocally.has(guid) ||
+           this.deleteRemotely.has(guid);
+  }
+
   /**
    * Merges two nodes, recursively walking folders.
    *
    * @param  {String} guid
    *         The GUID to use for the merged node.
    * @param  {BookmarkNode?} localNode
    *         The local node. May be `null` if the node only exists remotely.
    * @param  {BookmarkNode?} remoteNode

--- a/toolkit/components/places/tests/sync/test_bookmark_deletion.js
+++ b/toolkit/components/places/tests/sync/test_bookmark_deletion.js
@@ -580,8 +580,72 @@ add_task(async function test_move_to_new
       title: "mobile",
     }],
   }, "Should move C to closest surviving parent");
 
   await buf.finalize();
   await PlacesUtils.bookmarks.eraseEverything();
   await PlacesSyncUtils.bookmarks.reset();
 });
+
+add_task(async function test_nonexistent_on_one_side() {
+  let buf = await openMirror("nonexistent_on_one_side");
+
+  info("Set up empty mirror");
+  // Previous tests change the menu's date added time; reset it to a predictable
+  // value.
+  let menuDateAdded = new Date();
+  await PlacesUtils.bookmarks.update({
+    guid: PlacesUtils.bookmarks.menuGuid,
+    dateAdded: menuDateAdded,
+  });
+  await PlacesTestUtils.markBookmarksAsSynced();
+
+  // A doesn't exist in the mirror.
+  info("Create local tombstone for nonexistent remote item A");
+  await PlacesUtils.bookmarks.insert({
+    guid: "bookmarkAAAA",
+    parentGuid: PlacesUtils.bookmarks.menuGuid,
+    title: "A",
+    url: "http://example.com/a",
+    // Pretend a bookmark restore added A, so that we'll write a tombstone when
+    // we remove it.
+    source: PlacesUtils.bookmarks.SOURCES.IMPORT_REPLACE,
+  });
+  await PlacesUtils.bookmarks.remove("bookmarkAAAA");
+
+  // B doesn't exist in Places, and we don't currently persist tombstones (bug
+  // 1343103), so we should ignore it.
+  info("Create remote tombstone for nonexistent local item B");
+  await buf.store([{
+    id: "bookmarkBBBB",
+    deleted: true
+  }]);
+
+  info("Apply remote");
+  let changesToUpload = await buf.apply();
+  deepEqual(await buf.fetchUnmergedGuids(), ["bookmarkBBBB"],
+    "Should leave B unmerged");
+
+  // We should still upload a record for the menu, since we changed its
+  // children when we added then removed A.
+  deepEqual(changesToUpload, {
+    menu: {
+      tombstone: false,
+      counter: 2,
+      synced: false,
+      cleartext: {
+        id: "menu",
+        type: "folder",
+        parentid: "places",
+        hasDupe: false,
+        parentName: "",
+        dateAdded: menuDateAdded.getTime(),
+        title: "Bookmarks Menu",
+        children: [],
+      },
+    },
+  });
+
+  await buf.finalize();
+  await PlacesUtils.bookmarks.eraseEverything();
+  await PlacesSyncUtils.bookmarks.reset();
+});