--- a/services/sync/modules/engines.js
+++ b/services/sync/modules/engines.js
@@ -785,16 +785,19 @@ SyncEngine.prototype = {
   // If this is false, we'll throw, otherwise, we'll ignore the record and
   // continue. This currently can only happen due to the record being larger
   // than the record upload limit.
   allowSkippedRecord: true,
 
   // Which sortindex to use when retrieving records for this engine.
   _defaultSort: undefined,
 
+  // Does this engine persist incoming tombstones?
+  _storesTombstones: false,
+
   _metadataPostProcessor(json) {
     if (Array.isArray(json)) {
       // Pre-`JSONFile` storage stored an array, but `JSONFile` defaults to
       // an object, so we wrap the array for consistency.
       json = { ids: json };
     }
     if (!json.ids) {
       json.ids = [];
@@ -1446,36 +1449,56 @@ SyncEngine.prototype = {
    * Used by bookmark sync to merge folder child orders.
    */
   beforeRecordDiscard(localRecord, remoteRecord, remoteIsNewer) {
   },
 
   // Called when the server has a record marked as deleted, but locally we've
   // changed it more recently than the deletion. If we return false, the
   // record will be deleted locally. If we return true, we'll reupload the
-  // record to the server -- any extra work that's needed as part of this
-  // process should be done at this point (such as mark the record's parent
-  // for reuploading in the case of bookmarks).
+  // record to the server.
   async _shouldReviveRemotelyDeletedRecord(remoteItem) {
     return true;
   },
 
+  /**
+   * Only called for engines which persist tombstones. Set whatever state is
+   * needed to remove the remote zombie 'remoteItem' when uploading
+   */
+  async _deleteRemoteZombie(remoteItem) {
+    throw new Error("Override in subclass if _storesTombstones is true");
+  },
+
+  /**
+   * For engines which persist tombstones (_storesTombstones), should return
+   * true if we have a local tombstone for the given guid.
+   */
+  async _shouldPreferTombstone(guid) {
+    return false;
+  },
+
   async _deleteId(id) {
     await this._tracker.removeChangedID(id);
     this._noteDeletedId(id);
   },
 
   // Marks an ID for deletion at the end of the sync.
   _noteDeletedId(id) {
     if (this._delete.ids == null)
       this._delete.ids = [id];
     else
       this._delete.ids.push(id);
   },
 
+  // If our remote records carry a better timestamp than "modified",
+  // we should return that here.
+  _getRemoteTimestamp(item) {
+    return item.modified;
+  },
+
   async _switchItemToDupe(localDupeGUID, incomingItem) {
     // The local, duplicate ID is always deleted on the server.
     await this._deleteId(localDupeGUID);
 
     // We unconditionally change the item's ID in case the engine knows of
     // an item but doesn't expose it through itemExists. If the API
     // contract were stronger, this could be changed.
     this._log.debug("Switching local ID to incoming: " + localDupeGUID + " -> " +
@@ -1500,36 +1523,36 @@ SyncEngine.prototype = {
 
     // We start reconciling by collecting a bunch of state. We do this here
     // because some state may change during the course of this function and we
     // need to operate on the original values.
     let existsLocally   = await this._store.itemExists(item.id);
     let locallyModified = this._modified.has(item.id);
 
     // TODO Handle clock drift better. Tracked in bug 721181.
-    let remoteAge = Resource.serverTime - item.modified;
+    let remoteAge = Resource.serverTime - this._getRemoteTimestamp(item);
     let localAge  = locallyModified ?
       (Date.now() / 1000 - this._modified.getModifiedTimestamp(item.id)) : null;
     let remoteIsNewer = remoteAge < localAge;
 
     this._log.trace("Reconciling " + item.id + ". exists=" +
                     existsLocally + "; modified=" + locallyModified +
                     "; local age=" + localAge + "; incoming age=" +
                     remoteAge);
 
     // We handle deletions first so subsequent logic doesn't have to check
     // deleted flags.
     if (item.deleted) {
       // If the item doesn't exist locally, there is nothing for us to do. We
       // can't check for duplicates because the incoming record has no data
       // which can be used for duplicate detection.
       if (!existsLocally) {
-        this._log.trace("Ignoring incoming item because it was deleted and " +
-                        "the item does not exist locally.");
-        return false;
+        this._log.trace((this._storesTombstones ? "Storing" : "Ignoring") +
+                        " incoming tombstone because the item does not exist locally.");
+        return this._storesTombstones;
       }
 
       // We decide whether to process the deletion by comparing the record
       // ages. If the item is not modified locally, the remote side wins and
       // the deletion is processed. If it is modified locally, we take the
       // newer record.
       if (!locallyModified) {
         this._log.trace("Applying incoming delete because the local item " +
@@ -1545,16 +1568,25 @@ SyncEngine.prototype = {
       // If the local record is newer, we defer to individual engines for
       // how to handle this. By default, we revive the record.
       let willRevive = await this._shouldReviveRemotelyDeletedRecord(item);
       this._log.trace("Local record is newer -- reviving? " + willRevive);
 
       return !willRevive;
     }
 
+    // Check if we have a local tombstone, and delete the remote record if so.
+    if (!existsLocally && this._storesTombstones) {
+      if (await this._shouldPreferTombstone(item.id)) {
+        this._log.trace("Found local tombstone, Killing remote", item);
+        await this._deleteRemoteZombie(item);
+        return false;
+      }
+    }
+
     // At this point the incoming record is not for a deletion and must have
     // data. If the incoming record does not exist locally, we check for a local
     // duplicate existing under a different ID. The default implementation of
     // _findDupe() is empty, so engines have to opt in to this functionality.
     //
     // If we find a duplicate, we change the local ID to the incoming ID and we
     // refresh the metadata collected above. See bug 710448 for the history
     // of this logic.

--- a/services/sync/modules/engines/bookmarks.js
+++ b/services/sync/modules/engines/bookmarks.js
@@ -313,16 +313,18 @@ function BaseBookmarksEngine(service) {
 }
 BaseBookmarksEngine.prototype = {
   __proto__: SyncEngine.prototype,
   _recordObj: PlacesItem,
   _trackerObj: BookmarksTracker,
   version: 2,
   _defaultSort: "index",
 
+  _storesTombstones: true,
+
   syncPriority: 4,
   allowSkippedRecord: false,
 
   _migratedSyncMetadata: false,
   async _migrateSyncMetadata({ migrateLastSync = true } = {}) {
     if (this._migratedSyncMetadata) {
       return;
     }
@@ -637,26 +639,59 @@ BookmarksEngine.prototype = {
       }
       this._log.warn("Error while building GUID map, skipping all other incoming items", ex);
       // eslint-disable-next-line no-throw-literal
       throw {code: SyncEngine.prototype.eEngineAbortApplyIncoming,
              cause: ex};
     }
   },
 
+  async _deleteRemoteZombie(remoteItem) {
+    if (PlacesSyncUtils.bookmarks.ROOTS.includes(remoteItem.id)) {
+      this._log.error(`Bug: we somehow decided that ${remoteItem.id} was a zombie...`);
+      throw new Error("Roots items cannot be zombies!");
+    }
+    this._log.trace("Deleting remote 'zombie'", remoteItem);
+    let result = await PlacesSyncUtils.bookmarks.touchTombstone(remoteItem.id);
+    this._modified.insert(result);
+    // If we got the child, the parent (if it exists) is probably wrong, so we
+    // flag it for weak upload if we have any information about it.
+    if (await PlacesSyncUtils.bookmarks.isBookmarkOrTombstone(remoteItem.parentid)) {
+      this.addForWeakUpload(remoteItem.parentid);
+    }
+  },
+
+  // Returns true if `id` is a local tombstone record that should be preferred
+  // to an incoming record. Specifically, it's a local tombstone record with a
+  // syncStatus of UNKNOWN.
+  async _shouldPreferTombstone(id) {
+    let modStatus = this._modified.getSyncStatus(id);
+    if (!this._modified.isTombstone() || modStatus < 0) {
+      modStatus = await PlacesSyncUtils.bookmarks.getTombstoneSyncStatus(id);
+    }
+    return modStatus == PlacesUtils.bookmarks.SYNC_STATUS.UNKNOWN;
+  },
+
   async _deletePending() {
     // Delete pending items -- See the comment above BookmarkStore's deletePending
     let newlyModified = await this._store.deletePending();
     if (newlyModified) {
       this._log.debug("Deleted pending items", newlyModified);
       this._modified.insert(newlyModified);
     }
   },
 
   async _shouldReviveRemotelyDeletedRecord(item) {
+    // For items where SYNC_STATUS == UNKNOWN, we always prefer deletions (on
+    // either side).
+    let modStatus = this._modified.getSyncStatus(item.id);
+    if (modStatus == PlacesUtils.bookmarks.SYNC_STATUS.UNKNOWN) {
+      return false;
+    }
+
     let modifiedTimestamp = this._modified.getModifiedTimestamp(item.id);
     if (!modifiedTimestamp) {
       // We only expect this to be called with items locally modified, so
       // something strange is going on - play it safe and don't revive it.
       this._log.error("_shouldReviveRemotelyDeletedRecord called on unmodified item: " + item.id);
       return false;
     }
 
@@ -1122,28 +1157,26 @@ BookmarksStore.prototype = {
   //
   // - Additions, moves, and updates are processed before deletions.
   //     - To do this, all deletion operations are buffered in `this._itemsToDelete`
   //       during a sync.
   //     - The exception to this is the moves that occur to fix the order of bookmark
   //       children, which are performed after we process deletions.
   // - Non-folders are deleted before folder deletions, so that when we process
   //   folder deletions we know the correct state.
-  // - Remote deletions always win for folders, but do not result in recursive
-  //   deletion of children. This is a hack because we're not able to distinguish
-  //   between value changes and structural changes to folders, and we don't even
-  //   have the old server record to compare to. See `BookmarkEngine`'s
-  //   `_shouldReviveRemotelyDeletedRecord` method.
+  //
+  // - Remote deletions always win, but in the case of folders do not result in
+  //   recursive deletion of children. This is a hack because we're not able to
+  //   distinguish between value changes and structural changes to folders, and
+  //   we don't even have the old server record to compare to.
+  //
   // - When a folder is deleted, its remaining children are moved in order to
   //   their closest living ancestor.  If this is interrupted (unlikely, but
   //   possible given that we don't perform this operation in a transaction),
   //   we revive the folder.
-  // - Remote deletions can lose for non-folders, but only until we handle
-  //   bookmark restores correctly (removing stale state from the server -- this
-  //   is to say, if bug 1230011 is fixed, we should never revive bookmarks).
   //
   // See `PlacesSyncUtils.bookmarks.remove` for the implementation.
 
   async deletePending() {
     let guidsToUpdate = await PlacesSyncUtils.bookmarks.remove([...this._itemsToDelete]);
     this.clearPendingDeletions();
     return guidsToUpdate;
   },
@@ -1488,9 +1521,17 @@ class BookmarksChangeset extends Buffere
 
   isTombstone(id) {
     let change = this.changes[id];
     if (change) {
       return change.tombstone;
     }
     return false;
   }
+
+  getSyncStatus(id) {
+    let change = this.changes[id];
+    if (change) {
+      return change.status;
+    }
+    return -1;
+  }
 }

--- a/services/sync/tests/unit/test_bookmark_tombstones.js
+++ b/services/sync/tests/unit/test_bookmark_tombstones.js
@@ -89,25 +89,20 @@ add_task(async function test_general() {
     _("And add a new non-tombstone remote bookmark");
     let {id: id3} = collection.insertRecord(
       makeBookmark({ parentid: "menu", title: "69105" }));
 
     collection.updateRecord("menu", record => {
       record.children.push(id3);
     }, Date.now() / 1000);
     engine.lastSync = Date.now() / 1000 - 30;
-
-    await sync_engine_and_validate_telem(engine, false);
-
-    ok(await engine._isStoredTombstone(id0), "Shouldn't revive record");
+    // Reset the local sync ID, forcing us to prefer deletions over local records.
+    await engine.resetLocalSyncID();
 
-    ok(collection.cleartext(id0).deleted, "Should reupload tombstone");
-
-    ok(!(await PlacesSyncUtils.bookmarks.fetchChildRecordIds("toolbar")).includes(id0),
-       "Parent shouldn't have the zombie locally");
+    await sync_engine_and_validate_telem(engine, true);
 
     ok(!collection.cleartext("toolbar").children.includes(id0),
        "Parent shouldn't have the zombie remotely");
 
     ok((await PlacesSyncUtils.bookmarks.fetchChildRecordIds("menu")).includes(id3),
        "Should the apply updated parent without issue");
 
     equal((await PlacesUtils.bookmarks.fetch(id3)).title, "69105",

--- a/toolkit/components/places/PlacesSyncUtils.jsm
+++ b/toolkit/components/places/PlacesSyncUtils.jsm
@@ -1443,16 +1443,27 @@ const BookmarkSyncUtils = PlacesSyncUtil
     PlacesUtils.SYNC_BOOKMARK_VALIDATORS.recordId(recordId);
     let guid = BookmarkSyncUtils.recordIdToGuid(recordId);
     let db = await PlacesUtils.promiseDBConnection();
     let result = await tombstoneDateRemoved(db, guid);
     return result >= 0;
   },
 
   /**
+   * Returns the syncStatus of a tombstone record. If the provided ID
+   * isn't a tombstone, returns -1.
+   */
+  async getTombstoneSyncStatus(recordId) {
+    PlacesUtils.SYNC_BOOKMARK_VALIDATORS.recordId(recordId);
+    let guid = BookmarkSyncUtils.recordIdToGuid(recordId);
+    let db = await PlacesUtils.promiseDBConnection();
+    return tombstoneSyncStatus(db, guid);
+  },
+
+  /**
    * Fetch the set of all tombstones. Or, at least their `guid`s at least.
    * Used for validation.
    */
   async promiseAllTombstones() {
     let db = await PlacesUtils.promiseDBConnection();
     let rows = await db.executeCached(`
       SELECT guid FROM moz_bookmarks_deleted
     `);
@@ -2303,16 +2314,29 @@ async function tombstoneDateRemoved(db, 
   );
   if (!rows.length) {
     return -1;
   }
   let removedPRTime = rows[0].getResultByName("dateRemoved");
   return removedPRTime / MICROSECONDS_PER_SECOND;
 }
 
+async function tombstoneSyncStatus(db, guid) {
+  let rows = await db.executeCached(`
+    SELECT syncStatus
+    FROM moz_bookmarks_deleted
+    WHERE guid = :guid`,
+    { guid }
+  );
+  if (!rows.length) {
+    return -1;
+  }
+  return rows.getResultByName("syncStatus");
+}
+
 function addRowToChangeRecords(row, changeRecords) {
   let guid = row.getResultByName("guid");
   if (!guid) {
     throw new Error(`Changed item missing GUID`);
   }
   let isTombstone = !!row.getResultByName("tombstone");
   let recordId = BookmarkSyncUtils.guidToRecordId(guid);
   if (recordId in changeRecords) {