--- a/services/sync/modules/engines.js
+++ b/services/sync/modules/engines.js
@@ -126,47 +126,59 @@ Tracker.prototype = {
   },
 
   unignoreID: function (id) {
     let index = this._ignored.indexOf(id);
     if (index != -1)
       this._ignored.splice(index, 1);
   },
 
+  _isIgnored(id) {
+    return this.ignoreAll || (id in this._ignored);
+  },
+
+  _saveChangedID(id, when) {
+    this._log.trace("Adding changed ID: " + id + ", " + when);
+    this.changedIDs[id] = when;
+    this.saveChangedIDs(this.onSavedChangedIDs);
+  },
+
+  _now() {
+    return Math.floor(Date.now() / 1000);
+  },
+
   addChangedID: function (id, when) {
     if (!id) {
       this._log.warn("Attempted to add undefined ID to tracker");
       return false;
     }
 
-    if (this.ignoreAll || (id in this._ignored)) {
+    if (this._isIgnored(id)) {
       return false;
     }
 
     // Default to the current time in seconds if no time is provided.
     if (when == null) {
-      when = Math.floor(Date.now() / 1000);
+      when = this._now();
     }
 
     // Add/update the entry if we have a newer time.
     if ((this.changedIDs[id] || -Infinity) < when) {
-      this._log.trace("Adding changed ID: " + id + ", " + when);
-      this.changedIDs[id] = when;
-      this.saveChangedIDs(this.onSavedChangedIDs);
+      this._saveChangedID(id, when);
     }
 
     return true;
   },
 
   removeChangedID: function (id) {
     if (!id) {
       this._log.warn("Attempted to remove undefined ID to tracker");
       return false;
     }
-    if (this.ignoreAll || (id in this._ignored))
+    if (this._isIgnored(id))
       return false;
     if (this.changedIDs[id] != null) {
       this._log.trace("Removing changed ID " + id);
       delete this.changedIDs[id];
       this.saveChangedIDs();
     }
     return true;
   },
@@ -851,24 +863,37 @@ SyncEngine.prototype = {
     return parseInt(Svc.Prefs.get(this.name + ".lastSyncLocal", "0"), 10);
   },
   set lastSyncLocal(value) {
     // Store as a string because pref can only store C longs as numbers.
     Svc.Prefs.set(this.name + ".lastSyncLocal", value.toString());
   },
 
   /*
-   * Returns a mapping of IDs -> changed timestamp. Engine implementations
-   * can override this method to bypass the tracker for certain or all
-   * changed items.
+   * Returns an initial changeset for this sync. The changeset is an object that
+   * maps IDs -> opaque change record. Engine implementations can override this
+   * method to bypass the tracker for certain or all changed items.
    */
   getChangedIDs: function () {
     return this._tracker.changedIDs;
   },
 
+  /**
+   * Returns an initial changeset containing all local IDs. This is only called
+   * on the first sync; subsequent syncs use `getChangedIDs`.
+   */
+  getAllIDs() {
+    // Mark all items to be uploaded, but treat them as changed from long ago
+    let modified = {};
+    for (let id in this._store.getAllIDs()) {
+      modified[id] = 0;
+    }
+    return modified;
+  },
+
   // Create a new record using the store and add in crypto fields.
   _createRecord: function (id) {
     let record = this._store.createRecord(id, this.name);
     record.id = id;
     record.collection = this.name;
     return record;
   },
 
@@ -923,22 +948,18 @@ SyncEngine.prototype = {
     // upload objects we remove them from this._modified. If an error occurs
     // or any objects fail to upload, they will remain in this._modified. At
     // the end of a sync, or after an error, we add all objects remaining in
     // this._modified to the tracker.
     this.lastSyncLocal = Date.now();
     if (this.lastSync) {
       this._modified = this.getChangedIDs();
     } else {
-      // Mark all items to be uploaded, but treat them as changed from long ago
       this._log.debug("First sync, uploading all items");
-      this._modified = {};
-      for (let id in this._store.getAllIDs()) {
-        this._modified[id] = 0;
-      }
+      this._modified = this.getAllIDs();
     }
     // Clear the tracker now. If the sync fails we'll add the ones we failed
     // to upload back.
     this._tracker.clearChangedIDs();
 
     this._log.info(Object.keys(this._modified).length +
                    " outgoing items pre-reconciliation");
 
@@ -1252,25 +1273,59 @@ SyncEngine.prototype = {
    * @return GUID of the similar item; falsy otherwise
    */
   _findDupe: function (item) {
     // By default, assume there's no dupe items for the engine
   },
 
   _deleteId: function (id) {
     this._tracker.removeChangedID(id);
+    this._noteDeletedId(id);
+  },
 
-    // Remember this id to delete at the end of sync
+  // 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);
   },
 
   /**
+   * Methods to query and update the changeset for the current sync. The
+   * changeset is an object keyed by the record ID, with opaque values.
+   * By default, the value is a timestamp, though the bookmarks engine
+   * returns change records with additional data.
+   */
+
+  // Returns the last modified time, in seconds, for an entry in the changeset.
+  // `id` is guaranteed to be in the set.
+  _getModifiedTimestamp(id) {
+    return this._modified[id];
+  },
+
+  // Indicates whether an entry is in the changeset.
+  _isModified(id) {
+    return id in this._modified;
+  },
+
+  // Removes an entry from the changeset. Used to remove entries for reconciled
+  // and successfully uploaded records.
+  _clearModified(id) {
+    delete this._modified[id];
+  },
+
+  // Swaps two entries in the changeset. Used when reconciling duplicates that
+  // have local changes.
+  _replaceModified(oldID, newID) {
+    this._modified[newID] = this._modified[oldID];
+    delete this._modified[oldID];
+  },
+
+  /**
    * Reconcile incoming record with local state.
    *
    * This function essentially determines whether to apply an incoming record.
    *
    * @param  item
    *         Record from server to be tested for application.
    * @return boolean
    *         Truthy if incoming record should be applied. False if not.
@@ -1279,22 +1334,22 @@ SyncEngine.prototype = {
     if (this._log.level <= Log.Level.Trace) {
       this._log.trace("Incoming: " + item);
     }
 
     // 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   = this._store.itemExists(item.id);
-    let locallyModified = item.id in this._modified;
+    let locallyModified = this._isModified(item.id);
 
     // TODO Handle clock drift better. Tracked in bug 721181.
     let remoteAge = AsyncResource.serverTime - item.modified;
     let localAge  = locallyModified ?
-      (Date.now() / 1000 - this._modified[item.id]) : null;
+      (Date.now() / 1000 - this._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
@@ -1355,23 +1410,22 @@ SyncEngine.prototype = {
         // 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: " + dupeID + " -> " +
                         item.id);
         this._store.changeItemID(dupeID, item.id);
 
         // If the local item was modified, we carry its metadata forward so
         // appropriate reconciling can be performed.
-        if (dupeID in this._modified) {
+        if (this._isModified(dupeID)) {
           locallyModified = true;
-          localAge = Date.now() / 1000 - this._modified[dupeID];
+          localAge = Date.now() / 1000 - this._getModifiedTimestamp(dupeID);
           remoteIsNewer = remoteAge < localAge;
 
-          this._modified[item.id] = this._modified[dupeID];
-          delete this._modified[dupeID];
+          this._replaceModified(dupeID, item.id);
         } else {
           locallyModified = false;
           localAge = null;
         }
 
         this._log.debug("Local item after duplication: age=" + localAge +
                         "; modified=" + locallyModified + "; exists=" +
                         existsLocally);
@@ -1395,17 +1449,17 @@ SyncEngine.prototype = {
       }
 
       // If the item was modified locally but isn't present, it must have
       // been deleted. If the incoming record is younger, we restore from
       // that record.
       if (remoteIsNewer) {
         this._log.trace("Applying incoming because local item was deleted " +
                         "before the incoming item was changed.");
-        delete this._modified[item.id];
+        this._clearModified(item.id);
         return true;
       }
 
       this._log.trace("Ignoring incoming item because the local item's " +
                       "deletion is newer.");
       return false;
     }
 
@@ -1421,17 +1475,17 @@ SyncEngine.prototype = {
 
     // If the records are the same, we don't need to do anything. This does
     // potentially throw away a local modification time. But, if the records
     // are the same, does it matter?
     if (recordsEqual) {
       this._log.trace("Ignoring incoming item because the local item is " +
                       "identical.");
 
-      delete this._modified[item.id];
+      this._clearModified(item.id);
       return false;
     }
 
     // At this point the records are different.
 
     // If we have no local modifications, always take the server record.
     if (!locallyModified) {
       this._log.trace("Applying incoming record because no local conflicts.");
@@ -1477,17 +1531,17 @@ SyncEngine.prototype = {
         if (failed_ids.length)
           this._log.debug("Records that will be uploaded again because "
                           + "the server couldn't store them: "
                           + failed_ids.join(", "));
 
         // Clear successfully uploaded objects.
         const succeeded_ids = Object.values(resp.obj.success);
         for (let id of succeeded_ids) {
-          delete this._modified[id];
+          this._clearModified(id);
         }
 
         this._onRecordsWritten(succeeded_ids, failed_ids);
       }
 
       let postQueue = up.newPostQueue(this._log, handleResponse);
 
       for (let id of modifiedIDs) {

--- a/services/sync/modules/engines/bookmarks.js
+++ b/services/sync/modules/engines/bookmarks.js
@@ -413,17 +413,56 @@ BookmarksEngine.prototype = {
       this._log.trace(item.id + " already a dupe: not finding one.");
       return;
     }
     let mapped = this._mapDupe(item);
     this._log.debug(item.id + " mapped to " + mapped);
     // We must return a string, not an object, and the entries in the GUIDMap
     // are created via "new String()" making them an object.
     return mapped ? mapped.toString() : mapped;
-  }
+  },
+
+  getAllIDs() {
+    return this._store.getAllIDs();
+  },
+
+  getChangedIDs() {
+    return this._tracker.getChangedIDs();
+  },
+
+  _deleteId(id) {
+    this._clearModified(id);
+    this._noteDeletedId(id);
+  },
+
+  // We only need to override `_getModifiedTimestamp` and `_clearModified`.
+  // `_replaceModified` already does the right thing, since we call
+  // `changeItemID` before replacing the update metadata, and `changeItemID`
+  // carries over the change counter.
+
+  _getModifiedTimestamp(id) {
+    let change = this._modified[id];
+    if (!change || change.synced) {
+      // Pretend the change doesn't exist if we've already marked it as
+      // uploaded or reconciled.
+      return Number.NaN;
+    }
+    return change.modified;
+  },
+
+  _isModified(id) {
+    return id in this._modified && !this._modified[id].synced;
+  },
+
+  _clearModified(id) {
+    let change = this._modified[id];
+    if (change) {
+      change.synced = true;
+    }
+  },
 };
 
 function BookmarksStore(name, engine) {
   Store.call(this, name, engine);
 
   // Explicitly nullify our references to our cached services so we don't leak
   Svc.Obs.add("places-shutdown", function() {
     for (let query in this._stmts) {
@@ -833,38 +872,39 @@ BookmarksStore.prototype = {
 
     if (node.type == node.RESULT_TYPE_FOLDER) {
       node.QueryInterface(Ci.nsINavHistoryQueryResultNode);
       node.containerOpen = true;
       try {
         // Remember all the children GUIDs and recursively get more
         for (let i = 0; i < node.childCount; i++) {
           let child = node.getChild(i);
-          items[this.GUIDForId(child.itemId)] = true;
+          items[this.GUIDForId(child.itemId)] = { modified: 0,
+                                                  deleted: false };
           this._getChildren(child, items);
         }
       }
       finally {
         node.containerOpen = false;
       }
     }
 
     return items;
   },
 
   getAllIDs: function BStore_getAllIDs() {
-    let items = {"menu": true,
-                 "toolbar": true,
-                 "unfiled": true,
+    let items = {"menu": { modified: 0, deleted: false },
+                 "toolbar": { modified: 0, deleted: false },
+                 "unfiled": { modified: 0, deleted: false },
                 };
     // We also want "mobile" but only if a local mobile folder already exists
     // (otherwise we'll later end up creating it, which we want to avoid until
     // we actually need it.)
     if (BookmarkSpecialIds.findMobileRoot(false)) {
-      items["mobile"] = true;
+      items["mobile"] = { modified: 0, deleted: false };
     }
     for (let guid of BookmarkSpecialIds.guids) {
       if (guid != "places" && guid != "tags")
         this._getChildren(guid, items);
     }
     return items;
   },
 
@@ -944,25 +984,177 @@ BookmarksTracker.prototype = {
   },
 
   QueryInterface: XPCOMUtils.generateQI([
     Ci.nsINavBookmarkObserver,
     Ci.nsINavBookmarkObserver_MOZILLA_1_9_1_ADDITIONS,
     Ci.nsISupportsWeakReference
   ]),
 
+  addChangedID(id, change) {
+    if (!id) {
+      this._log.warn("Attempted to add undefined ID to tracker");
+      return false;
+    }
+    if (this._isIgnored(id)) {
+      return false;
+    }
+    let modified = -Infinity;
+    if (this.changedIDs[id]) {
+      let timestamp = this.changedIDs[id];
+      // Allow raw timestamps for backward-compatibility with persisted
+      // changed IDs. The new format uses tuples to track deleted items.
+      modified = typeof timestamp == "number" ? timestamp : timestamp.modified;
+    }
+    if (modified < change.modified) {
+      this._saveChangedID(id, change);
+    }
+    return true;
+  },
+
+  getChangedIDs() {
+    // Ignore deleted items when querying the database, so that we don't
+    // remove deletions from the tracker.
+    let changedGUIDs = this._getChangedPlacesGUIDs();
+    if (!changedGUIDs.length) {
+      return this.changedIDs;
+    }
+
+    let tombstones = changedGUIDs.filter(info => info.deleted);
+
+    // We can't use `PlacesUtils.promiseDBConnection` here, because we run Sync
+    // in batch mode, which means this query won't see any changes until the
+    // batch finishes and the transaction commits.
+    let db = PlacesUtils.history.QueryInterface(Ci.nsPIPlacesDatabase)
+                        .DBConnection;
+
+    // Filter out tags, organizer queries, and other descendants that we're
+    // not tracking. This builds up a SQL query with 3-4 CTEs, depending on
+    // whether we have any tombstones.
+    let expressions = [];
+
+    if (tombstones.length) {
+      // A CTE containing all tombstone GUIDs.
+      expressions.push(`
+        tombstones(guid, parentGuid) AS (
+          VALUES ${tombstones.map(info =>
+            `(${JSON.stringify(info.placesGUID)}, ${JSON.stringify(info.placesParentGUID)})`
+          ).join()}
+        )
+      `);
+    }
+    // A CTE with all tracked changes, including tombstones and modifications.
+    expressions.push(`
+      changes(guid) AS (
+        VALUES ${changedGUIDs.map(info =>
+          `(${JSON.stringify(info.placesGUID)})`
+        ).join()}
+      )
+    `);
+    // A CTE with all tracked bookmarks, tombstones, and their parents.
+    {
+      let bookmarksQuery = [`
+        SELECT b.guid, p.guid
+        FROM moz_bookmarks b
+        JOIN moz_bookmarks p ON p.id = b.parent
+      `];
+      if (tombstones.length) {
+        bookmarksQuery.push(`SELECT guid, parentGuid FROM tombstones`);
+      }
+      expressions.push(`bookmarks(guid, parentGuid) AS (${
+        bookmarksQuery.join(" UNION ALL ")
+      })`);
+    }
+    // A recursive CTE containing all children for every root that we track
+    // (excluding tags, organizer queries, and any other bookmark that's not
+    // in one of the change roots), plus any tombstones with unknown ancestors.
+    {
+      let syncedItemsQuery = [`
+        SELECT guid
+        FROM moz_bookmarks
+        WHERE id IN (${getChangeRootIds().join(", ")})
+      `];
+      if (tombstones.length) {
+        // Make sure we include orphan tombstones, if we can't reconstruct
+        // the ancestor hierarchy. This can happen if we miss a deletion of
+        // a parent or an ancestor because the tracker isn't listening for
+        // changes.
+        syncedItemsQuery.push(`
+          SELECT parentGuid
+          FROM tombstones
+          WHERE parentGuid NOT IN (SELECT guid FROM bookmarks)
+        `);
+      }
+      syncedItemsQuery.push(`
+        SELECT guid
+        FROM bookmarks
+        JOIN syncedItems ON parentGuid = syncedGuid
+      `);
+      expressions.push(`syncedItems(syncedGuid) AS (${
+        syncedItemsQuery.join(" UNION ALL ")
+      })`);
+    }
+
+    let query = `
+      WITH RECURSIVE ${expressions.join(", ")}
+      SELECT syncedGuid AS guid
+      FROM syncedItems
+    `;
+
+    let statement = db.createAsyncStatement(query);
+    try {
+      let results = Async.querySpinningly(statement, ["guid"]);
+      let descendantGuids = new Set(results.map(result => result.guid));
+
+      for (let { syncID, placesGUID } of changedGUIDs) {
+        if (!descendantGuids.has(placesGUID)) {
+          this.removeChangedID(syncID);
+        }
+      }
+    } finally {
+      statement.finalize();
+    }
+
+    return this.changedIDs;
+  },
+
+  // Returns an array of changed Places GUIDs, excluding deleted items.
+  _getChangedPlacesGUIDs() {
+    let guids = []; // { deleted, modified }
+    for (let syncID in this.changedIDs) {
+      let placesGUID = BookmarkSpecialIds.syncIDToPlacesGUID(syncID);
+      if (this.changedIDs[syncID].deleted === true) {
+        // The `===` check filters out deleted items and persisted raw
+        // timestamps, which won't have a `deleted` property.
+        guids.push({
+          deleted: true,
+          syncID,
+          placesGUID,
+          placesParentGUID: this.changedIDs[syncID].parentGUID,
+        });
+        continue;
+      }
+      guids.push({ syncID, placesGUID });
+    }
+    return guids;
+  },
+
   /**
    * Add a bookmark GUID to be uploaded and bump up the sync score.
    *
    * @param itemGuid
    *        GUID of the bookmark to upload.
    */
-  _add: function BMT__add(itemId, guid) {
+  _add: function BMT__add(itemId, guid, deleted = false, parentGUID) {
     guid = BookmarkSpecialIds.specialGUIDForId(itemId) || guid;
-    if (this.addChangedID(guid))
+    let info = { modified: this._now(), deleted };
+    if (deleted) {
+      info.parentGUID = parentGUID;
+    }
+    if (this.addChangedID(guid, info))
       this._upScore();
   },
 
   /* Every add/remove/change will trigger a sync for MULTI_DEVICE (except in
      a batch operation, where we do it at the end of the batch) */
   _upScore: function BMT__upScore() {
     if (this._batchDepth == 0) {
       this.score += SCORE_INCREMENT_XLARGE;
@@ -979,45 +1171,16 @@ BookmarksTracker.prototype = {
    * @param folder (optional)
    *        Folder of the item being changed
    */
   _ignore: function BMT__ignore(itemId, folder, guid) {
     // Ignore unconditionally if the engine tells us to.
     if (this.ignoreAll)
       return true;
 
-    // Get the folder id if we weren't given one.
-    if (folder == null) {
-      try {
-        folder = PlacesUtils.bookmarks.getFolderIdForItem(itemId);
-      } catch (ex) {
-        this._log.debug("getFolderIdForItem(" + itemId +
-                        ") threw; calling _ensureMobileQuery.");
-        // I'm guessing that gFIFI can throw, and perhaps that's why
-        // _ensureMobileQuery is here at all. Try not to call it.
-        this._ensureMobileQuery();
-        folder = PlacesUtils.bookmarks.getFolderIdForItem(itemId);
-      }
-    }
-
-    // Ignore changes to tags (folders under the tags folder).
-    let tags = BookmarkSpecialIds.tags;
-    if (folder == tags)
-      return true;
-
-    // Ignore tag items (the actual instance of a tag for a bookmark).
-    if (PlacesUtils.bookmarks.getFolderIdForItem(folder) == tags)
-      return true;
-
-    // Make sure to remove items that have the exclude annotation.
-    if (PlacesUtils.annotations.itemHasAnnotation(itemId, BookmarkAnnos.EXCLUDEBACKUP_ANNO)) {
-      this.removeChangedID(guid);
-      return true;
-    }
-
     return false;
   },
 
   onItemAdded: function BMT_onItemAdded(itemId, folder, index,
                                         itemType, uri, title, dateAdded,
                                         guid, parentGuid) {
     if (this._ignore(itemId, folder, guid))
       return;
@@ -1029,17 +1192,17 @@ BookmarksTracker.prototype = {
 
   onItemRemoved: function (itemId, parentId, index, type, uri,
                            guid, parentGuid) {
     if (this._ignore(itemId, parentId, guid)) {
       return;
     }
 
     this._log.trace("onItemRemoved: " + itemId);
-    this._add(itemId, guid);
+    this._add(itemId, guid, /* deleted */ true, parentGuid);
     this._add(parentId, parentGuid);
   },
 
   _ensureMobileQuery: function _ensureMobileQuery() {
     let find = val =>
       PlacesUtils.annotations.getItemsWithAnnotation(BookmarkAnnos.ORGANIZERQUERY_ANNO, {}).filter(
         id => PlacesUtils.annotations.getItemAnnotation(id, BookmarkAnnos.ORGANIZERQUERY_ANNO) == val
       );
@@ -1127,8 +1290,24 @@ BookmarksTracker.prototype = {
   onEndUpdateBatch: function () {
     if (--this._batchDepth === 0 && this._batchSawScoreIncrement) {
       this.score += SCORE_INCREMENT_XLARGE;
       this._batchSawScoreIncrement = false;
     }
   },
   onItemVisited: function () {}
 };
+
+// Returns an array of root IDs to recursively query for synced bookmarks.
+// Items in other roots, including tags and organizer queries, will be
+// ignored.
+function getChangeRootIds() {
+  let rootIds = [
+    PlacesUtils.bookmarksMenuFolderId,
+    PlacesUtils.toolbarFolderId,
+    PlacesUtils.unfiledBookmarksFolderId,
+  ];
+  let mobileRootId = BookmarkSpecialIds.findMobileRoot(false);
+  if (mobileRootId) {
+    rootIds.push(mobileRootId);
+  }
+  return rootIds;
+}

--- a/services/sync/tests/unit/test_bookmark_tracker.js
+++ b/services/sync/tests/unit/test_bookmark_tracker.js
@@ -17,17 +17,17 @@ var tracker = engine._tracker;
 
 store.wipe();
 tracker.persistChangedIDs = false;
 
 const DAY_IN_MS = 24 * 60 * 60 * 1000;
 
 // Test helpers.
 function* verifyTrackerEmpty() {
-  do_check_empty(tracker.changedIDs);
+  do_check_empty(tracker.getChangedIDs());
   do_check_eq(tracker.score, 0);
 }
 
 function* resetTracker() {
   tracker.clearChangedIDs();
   tracker.resetScore();
 }
 
@@ -43,27 +43,27 @@ function* startTracking() {
   Svc.Obs.notify("weave:engine:start-tracking");
 }
 
 function* stopTracking() {
   Svc.Obs.notify("weave:engine:stop-tracking");
 }
 
 function* verifyTrackedItems(tracked) {
-  let trackedIDs = new Set(Object.keys(tracker.changedIDs));
+  let trackedIDs = new Set(Object.keys(tracker.getChangedIDs()));
   for (let guid of tracked) {
-    ok(tracker.changedIDs[guid] > 0, `${guid} should be tracked`);
+    ok(tracker.changedIDs[guid].modified > 0, `${guid} should be tracked`);
     trackedIDs.delete(guid);
   }
   equal(trackedIDs.size, 0, `Unhandled tracked IDs: ${
     JSON.stringify(Array.from(trackedIDs))}`);
 }
 
 function* verifyTrackedCount(expected) {
-  do_check_attribute_count(tracker.changedIDs, expected);
+  do_check_attribute_count(tracker.getChangedIDs(), expected);
 }
 
 add_task(function* test_tracking() {
   _("Test starting and stopping the tracker");
 
   let folder = PlacesUtils.bookmarks.createFolder(
     PlacesUtils.bookmarks.bookmarksMenuFolder,
     "Test Folder", PlacesUtils.bookmarks.DEFAULT_INDEX);
@@ -384,17 +384,17 @@ add_task(function* test_onItemTagged() {
 
     yield startTracking();
 
     _("Tag the item");
     PlacesUtils.tagging.tagURI(uri, ["foo"]);
 
     // bookmark should be tracked, folder should not be.
     yield verifyTrackedItems([bGUID]);
-    do_check_eq(tracker.score, SCORE_INCREMENT_XLARGE);
+    do_check_eq(tracker.score, SCORE_INCREMENT_XLARGE * 5);
   } finally {
     _("Clean up.");
     yield cleanup();
   }
 });
 
 add_task(function* test_onItemUntagged() {
   _("Items untagged using the synchronous API should be tracked");
@@ -416,17 +416,17 @@ add_task(function* test_onItemUntagged()
     PlacesUtils.tagging.tagURI(uri, ["foo"]);
 
     yield startTracking();
 
     _("Remove the tag");
     PlacesUtils.tagging.untagURI(uri, ["foo"]);
 
     yield verifyTrackedItems([fx1GUID, fx2GUID]);
-    do_check_eq(tracker.score, SCORE_INCREMENT_XLARGE * 2);
+    do_check_eq(tracker.score, SCORE_INCREMENT_XLARGE * 6);
   } finally {
     _("Clean up.");
     yield cleanup();
   }
 });
 
 add_task(function* test_async_onItemUntagged() {
   _("Items untagged using the asynchronous API should be tracked");
@@ -459,17 +459,17 @@ add_task(function* test_async_onItemUnta
     });
 
     yield startTracking();
 
     _("Remove the tag using the async bookmarks API");
     yield PlacesUtils.bookmarks.remove(fxTag.guid);
 
     yield verifyTrackedItems([fxBmk1.guid, fxBmk2.guid]);
-    do_check_eq(tracker.score, SCORE_INCREMENT_XLARGE * 2);
+    do_check_eq(tracker.score, SCORE_INCREMENT_XLARGE * 6);
   } finally {
     _("Clean up.");
     yield cleanup();
   }
 });
 
 add_task(function* test_async_onItemTagged() {
   _("Items tagged using the asynchronous API should be tracked");
@@ -517,17 +517,17 @@ add_task(function* test_async_onItemTagg
     _("Tag an item using the async bookmarks API");
     yield PlacesUtils.bookmarks.insert({
       type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
       parentGuid: tag.guid,
       url: "http://getfirefox.com",
     });
 
     yield verifyTrackedItems([fxBmk1.guid, fxBmk2.guid]);
-    do_check_eq(tracker.score, SCORE_INCREMENT_XLARGE * 2);
+    do_check_eq(tracker.score, SCORE_INCREMENT_XLARGE * 6);
   } finally {
     _("Clean up.");
     yield cleanup();
   }
 });
 
 add_task(function* test_onItemKeywordChanged() {
   _("Keyword changes via the synchronous API should be tracked");
@@ -695,47 +695,16 @@ add_task(function* test_onItemAnnoChange
     yield verifyTrackedItems([bGUID]);
     do_check_eq(tracker.score, SCORE_INCREMENT_XLARGE);
   } finally {
     _("Clean up.");
     yield cleanup();
   }
 });
 
-add_task(function* test_onItemExcluded() {
-  _("Items excluded from backups should not be tracked");
-
-  try {
-    yield stopTracking();
-
-    _("Create a bookmark");
-    let b = PlacesUtils.bookmarks.insertBookmark(
-      PlacesUtils.bookmarks.bookmarksMenuFolder,
-      Utils.makeURI("http://getfirefox.com"),
-      PlacesUtils.bookmarks.DEFAULT_INDEX, "Get Firefox!");
-    let bGUID = engine._store.GUIDForId(b);
-
-    yield startTracking();
-
-    _("Exclude the bookmark from backups");
-    PlacesUtils.annotations.setItemAnnotation(
-      b, BookmarkAnnos.EXCLUDEBACKUP_ANNO, "Don't back this up", 0,
-      PlacesUtils.annotations.EXPIRE_NEVER);
-
-    _("Modify the bookmark");
-    PlacesUtils.bookmarks.setItemTitle(b, "Download Firefox");
-
-    _("Excluded items should be ignored");
-    yield verifyTrackerEmpty();
-  } finally {
-    _("Clean up.");
-    yield cleanup();
-  }
-});
-
 add_task(function* test_onPageAnnoChanged() {
   _("Page annotations should not be tracked");
 
   try {
     yield stopTracking();
 
     _("Insert a bookmark without an annotation");
     let pageURI = Utils.makeURI("http://getfirefox.com");
@@ -1266,18 +1235,18 @@ add_task(function* test_async_onItemDele
       title: "Bugzilla",
     });
 
     yield startTracking();
 
     yield PlacesUtils.bookmarks.eraseEverything();
 
     yield verifyTrackedItems(["menu", mozBmk.guid, mdnBmk.guid, "toolbar",
-                              bugsFolder.guid]);
-    do_check_eq(tracker.score, SCORE_INCREMENT_XLARGE * 6);
+                              bugsFolder.guid, bzBmk.guid]);
+    do_check_eq(tracker.score, SCORE_INCREMENT_XLARGE * 8);
   } finally {
     _("Clean up.");
     yield cleanup();
   }
 });
 
 add_task(function* test_onItemDeleted_removeFolderChildren() {
   _("Removing a folder's children should track the folder and its children");