--- a/toolkit/components/places/PlacesDBUtils.jsm
+++ b/toolkit/components/places/PlacesDBUtils.jsm
@@ -830,16 +830,23 @@ this.PlacesDBUtils = {
       params: {
         syncStatus: PlacesUtils.bookmarks.SYNC_STATUS.NEW,
       },
     });
     cleanupStatements.push({
       query: "DROP TRIGGER moz_bm_fix_guids_temp_trigger",
     });
 
+    // S.2 drop tombstones for bookmarks that aren't deleted.
+    cleanupStatements.push({
+      query:
+      `DELETE FROM moz_bookmarks_deleted
+       WHERE guid IN (SELECT guid FROM moz_bookmarks)`,
+    });
+
     // MAINTENANCE STATEMENTS SHOULD GO ABOVE THIS POINT!
 
     return cleanupStatements;
   },
 
   /**
    * Tries to vacuum the database.
    *

--- a/toolkit/components/places/PlacesSyncUtils.jsm
+++ b/toolkit/components/places/PlacesSyncUtils.jsm
@@ -553,18 +553,17 @@ const BookmarkSyncUtils = PlacesSyncUtil
    *        A changeset containing sync change records, as returned by
    *        `pullChanges`.
    * @return {Promise} resolved once all records have been updated.
    */
   pushChanges(changeRecords) {
     return PlacesUtils.withConnectionWrapper(
       "BookmarkSyncUtils: pushChanges", async function(db) {
         let skippedCount = 0;
-        let syncedTombstoneGuids = [];
-        let syncedChanges = [];
+        let updateParams = [];
 
         for (let syncId in changeRecords) {
           // Validate change records to catch coding errors.
           let changeRecord = validateChangeRecord(
             "BookmarkSyncUtils: pushChanges",
             changeRecords[syncId], {
               tombstone: { required: true },
               counter: { required: true },
@@ -576,47 +575,49 @@ const BookmarkSyncUtils = PlacesSyncUtil
           // uploaded items. If upload failed, ignore the change; we'll
           // try again on the next sync.
           if (!changeRecord.synced) {
             skippedCount++;
             continue;
           }
 
           let guid = BookmarkSyncUtils.syncIdToGuid(syncId);
-          if (changeRecord.tombstone) {
-            syncedTombstoneGuids.push(guid);
-          } else {
-            syncedChanges.push([guid, changeRecord]);
-          }
+          updateParams.push({
+            guid,
+            syncChangeDelta: changeRecord.counter,
+            syncStatus: PlacesUtils.bookmarks.SYNC_STATUS.NORMAL,
+          });
         }
 
-        if (syncedChanges.length || syncedTombstoneGuids.length) {
+        // Reduce the change counter and update the sync status for
+        // reconciled and uploaded items. If the bookmark was updated
+        // during the sync, its change counter will still be > 0 for the
+        // next sync.
+        if (updateParams.length) {
           await db.executeTransaction(async function() {
-            for (let [guid, changeRecord] of syncedChanges) {
-              // Reduce the change counter and update the sync status for
-              // reconciled and uploaded items. If the bookmark was updated
-              // during the sync, its change counter will still be > 0 for the
-              // next sync.
-              await db.executeCached(`
-                UPDATE moz_bookmarks
-                SET syncChangeCounter = MAX(syncChangeCounter - :syncChangeDelta, 0),
-                    syncStatus = :syncStatus
-                WHERE guid = :guid`,
-                { guid, syncChangeDelta: changeRecord.counter,
-                  syncStatus: PlacesUtils.bookmarks.SYNC_STATUS.NORMAL });
-            }
+            await db.executeCached(`
+              UPDATE moz_bookmarks
+              SET syncChangeCounter = MAX(syncChangeCounter - :syncChangeDelta, 0),
+                  syncStatus = :syncStatus
+              WHERE guid = :guid`,
+              updateParams);
 
-            await removeTombstones(db, syncedTombstoneGuids);
+            // Unconditionally delete tombstones, in case the GUID exists in
+            // `moz_bookmarks` and `moz_bookmarks_deleted` (bug 1405563).
+            let deleteParams = updateParams.map(({ guid }) => ({ guid }));
+            await db.executeCached(`
+              DELETE FROM moz_bookmarks_deleted
+              WHERE guid = :guid`,
+              deleteParams);
           });
         }
 
         BookmarkSyncLog.debug(`pushChanges: Processed change records`,
                               { skipped: skippedCount,
-                                updated: syncedChanges.length,
-                                tombstones: syncedTombstoneGuids.length });
+                                updated: updateParams.length });
       }
     );
   },
 
   /**
    * Removes items from the database. Sync buffers incoming tombstones, and
    * calls this method to apply them at the end of each sync. Deletion
    * happens in three steps:
@@ -1960,32 +1961,51 @@ async function fetchQueryItem(db, bookma
   if (query) {
     item.query = query;
   }
 
   return item;
 }
 
 function addRowToChangeRecords(row, changeRecords) {
-  let syncId = BookmarkSyncUtils.guidToSyncId(row.getResultByName("guid"));
+  let guid = row.getResultByName("guid");
+  if (!guid) {
+    throw new Error(`Changed item missing GUID`);
+  }
+  let isTombstone = !!row.getResultByName("tombstone");
+  let syncId = BookmarkSyncUtils.guidToSyncId(guid);
   if (syncId in changeRecords) {
-    throw new Error(`Duplicate entry for ${syncId} in changeset`);
+    let existingRecord = changeRecords[syncId];
+    if (existingRecord.tombstone == isTombstone) {
+      // Should never happen: `moz_bookmarks.guid` has a unique index, and
+      // `moz_bookmarks_deleted.guid` is the primary key.
+      throw new Error(`Duplicate item or tombstone ${syncId} in changeset`);
+    }
+    if (!existingRecord.tombstone && isTombstone) {
+      // Don't replace undeleted items with tombstones...
+      BookmarkSyncLog.warn("addRowToChangeRecords: Ignoring tombstone for " +
+                           "undeleted item", syncId);
+      return;
+    }
+    // ...But replace undeleted tombstones with items.
+    BookmarkSyncLog.warn("addRowToChangeRecords: Replacing tombstone for " +
+                         "undeleted item", syncId);
   }
   let modifiedAsPRTime = row.getResultByName("modified");
   let modified = modifiedAsPRTime / MICROSECONDS_PER_SECOND;
   if (Number.isNaN(modified) || modified <= 0) {
     BookmarkSyncLog.error("addRowToChangeRecords: Invalid modified date for " +
                           syncId, modifiedAsPRTime);
     modified = 0;
   }
   changeRecords[syncId] = {
     modified,
     counter: row.getResultByName("syncChangeCounter"),
     status: row.getResultByName("syncStatus"),
-    tombstone: !!row.getResultByName("tombstone"),
+    tombstone: isTombstone,
     synced: false,
   };
 }
 
 /**
  * Queries the database for synced bookmarks and tombstones, and returns a
  * changeset for the Sync bookmarks engine.
  *

--- a/toolkit/components/places/tests/unit/test_preventive_maintenance.js
+++ b/toolkit/components/places/tests/unit/test_preventive_maintenance.js
@@ -1326,16 +1326,42 @@ tests.push({
     let tombstones = await PlacesTestUtils.fetchSyncTombstones();
     do_check_matches(tombstones.map(info => info.guid),
       ["bookmarkAAAA\n", "{123456}"]);
 
     await PlacesSyncUtils.bookmarks.reset();
   },
 });
 
+tests.push({
+  name: "S.2",
+  desc: "drop tombstones for bookmarks that aren't deleted",
+
+  async setup() {
+    addBookmark(null, bs.TYPE_BOOKMARK, bs.bookmarksMenuFolder, null, null,
+                "", "bookmarkAAAA");
+
+    await PlacesUtils.withConnectionWrapper("Insert tombstones", db =>
+      db.executeTransaction(async function() {
+        for (let guid of ["bookmarkAAAA", "bookmarkBBBB"]) {
+          await db.executeCached(`
+            INSERT INTO moz_bookmarks_deleted(guid)
+            VALUES(:guid)`,
+            { guid });
+        }
+      })
+    );
+  },
+
+  async check() {
+    let tombstones = await PlacesTestUtils.fetchSyncTombstones();
+    do_check_matches(tombstones.map(info => info.guid), ["bookmarkBBBB"]);
+  },
+});
+
 // ------------------------------------------------------------------------------
 
 tests.push({
   name: "Z",
   desc: "Sanity: Preventive maintenance does not touch valid items",
 
   _uri1: uri("http://www1.mozilla.org"),
   _uri2: uri("http://www2.mozilla.org"),

--- a/toolkit/components/places/tests/unit/test_sync_utils.js
+++ b/toolkit/components/places/tests/unit/test_sync_utils.js
@@ -2332,16 +2332,61 @@ add_task(async function test_pullChanges
       "Pulling changes should track synced sibling and parent");
     await setChangesSynced(changes);
   }
 
   await PlacesUtils.bookmarks.eraseEverything();
   await PlacesSyncUtils.bookmarks.reset();
 });
 
+add_task(async function test_pullChanges_tombstones() {
+  await ignoreChangedRoots();
+
+  do_print("Insert new bookmarks");
+  await PlacesUtils.bookmarks.insertTree({
+    guid: PlacesUtils.bookmarks.menuGuid,
+    children: [{
+      guid: "bookmarkAAAA",
+      url: "http://example.com/a",
+      title: "A",
+    }, {
+      guid: "bookmarkBBBB",
+      url: "http://example.com/b",
+      title: "B",
+    }],
+  });
+
+  do_print("Manually insert conflicting tombstone for new bookmark");
+  await PlacesUtils.withConnectionWrapper("test_pullChanges_tombstones",
+    async function(db) {
+      await db.executeCached(`
+        INSERT INTO moz_bookmarks_deleted(guid)
+        VALUES(:guid)`,
+        { guid: "bookmarkAAAA" });
+    }
+  );
+
+  let changes = await PlacesSyncUtils.bookmarks.pullChanges();
+  deepEqual(Object.keys(changes).sort(), ["bookmarkAAAA", "bookmarkBBBB",
+    "menu"], "Should handle undeleted items when returning changes");
+  strictEqual(changes.bookmarkAAAA.tombstone, false,
+    "Should replace tombstone for A with undeleted item");
+  strictEqual(changes.bookmarkBBBB.tombstone, false,
+    "Should not report B as deleted");
+
+  await setChangesSynced(changes);
+
+  let newChanges = await PlacesSyncUtils.bookmarks.pullChanges();
+  deepEqual(newChanges, {},
+    "Should not return changes after marking undeleted items as synced");
+
+  await PlacesUtils.bookmarks.eraseEverything();
+  await PlacesSyncUtils.bookmarks.reset();
+});
+
 add_task(async function test_pushChanges() {
   await ignoreChangedRoots();
 
   do_print("Populate test bookmarks");
   let guids = await populateTree(PlacesUtils.bookmarks.menuGuid, {
     kind: "bookmark",
     title: "unknownBmk",
     url: "https://example.org",