--- a/services/sync/modules/bookmark_repair.js
+++ b/services/sync/modules/bookmark_repair.js
@@ -165,16 +165,37 @@ class BookmarkRepairRequestor extends Co
       }
       ids.add(child);
     }
 
     // XXX - any others we should consider?
     return ids;
   }
 
+  _countServerOnlyFixableProblems(validationInfo) {
+    const fixableProblems = ["clientMissing", "serverMissing", "serverDeleted"];
+    return fixableProblems.reduce((numProblems, problemLabel) => {
+      return numProblems + validationInfo.problems[problemLabel].length;
+    }, 0);
+  }
+
+  tryServerOnlyRepairs(validationInfo) {
+    if (this._countServerOnlyFixableProblems(validationInfo) == 0) {
+      return false;
+    }
+    let engine = this.service.engineManager.get("bookmarks");
+    for (let id of validationInfo.problems.serverMissing) {
+      engine._modified.setWeak(id, { tombstone: false });
+    }
+    let toFetch = engine.toFetch.concat(validationInfo.problems.clientMissing,
+                                        validationInfo.problems.serverDeleted);
+    engine.toFetch = Array.from(new Set(toFetch));
+    return true;
+  }
+
   /* See if the repairer is willing and able to begin a repair process given
      the specified validation information.
      Returns true if a repair was started and false otherwise.
   */
   startRepairs(validationInfo, flowID) {
     if (this._currentState != STATE.NOT_REPAIRING) {
       log.info(`Can't start a repair - repair with ID ${this._flowID} is already in progress`);
       return false;

--- a/services/sync/modules/collection_repair.js
+++ b/services/sync/modules/collection_repair.js
@@ -63,16 +63,27 @@ function getRepairResponder(collection) 
 
 // The abstract classes.
 class CollectionRepairRequestor {
   constructor(service = null) {
     // allow service to be mocked in tests.
     this.service = service || Weave.Service;
   }
 
+  /* Try to resolve some issues with the server without involving other clients.
+     Returns true if we repaired some items.
+
+     @param   validationInfo       {Object}
+              The validation info as returned by the collection's validator.
+
+  */
+  tryServerOnlyRepairs(validationInfo) {
+    return false;
+  }
+
   /* See if the repairer is willing and able to begin a repair process given
      the specified validation information.
      Returns true if a repair was started and false otherwise.
 
      @param   validationInfo       {Object}
               The validation info as returned by the collection's validator.
 
      @param   flowID               {String}

--- a/services/sync/modules/doctor.js
+++ b/services/sync/modules/doctor.js
@@ -196,16 +196,20 @@ this.Doctor = {
     if (!this._shouldRepair(engine)) {
       log.info(`Skipping repair of ${engine.name} - disabled via preferences`);
       return;
     }
 
     let requestor = this._getRepairRequestor(engine.name);
     let didStart = false;
     if (requestor) {
+      if (requestor.tryServerOnlyRepairs(validationResults)) {
+        return; // TODO: It would be nice if we could request a validation to be
+                // done on next sync.
+      }
       didStart = requestor.startRepairs(validationResults, flowID);
     }
     log.info(`${didStart ? "did" : "didn't"} start a repair of ${engine.name} with flowID ${flowID}`);
   },
 
   _shouldRepair(engine) {
     return Svc.Prefs.get(`engine.${engine.name}.repair.enabled`, false);
   },

--- a/services/sync/tests/unit/test_bookmark_repair.js
+++ b/services/sync/tests/unit/test_bookmark_repair.js
@@ -315,10 +315,274 @@ add_task(async function test_bookmark_re
         numIDs: "0",
       },
     }]);
     await revalidationPromise;
     ok(!Services.prefs.prefHasUserValue("services.sync.repairs.bookmarks.state"),
       "Should clear repair pref after successfully completing repair");
   } finally {
     await cleanup(server);
+    clientsEngine = Service.clientsEngine = new ClientEngine(Service);
+  }
+});
+
+add_task(async function test_repair_client_missing() {
+  enableValidationPrefs();
+
+  _("Ensure that a record missing from the client only will get re-downloaded from the server");
+
+  let contents = {
+    meta: {
+      global: {
+        engines: {
+          clients: {
+            version: clientsEngine.version,
+            syncID: clientsEngine.syncID,
+          },
+          bookmarks: {
+            version: bookmarksEngine.version,
+            syncID: bookmarksEngine.syncID,
+          },
+        }
+      }
+    },
+    clients: {},
+    bookmarks: {},
+    crypto: {},
+  };
+  let server = serverForUsers({"foo": "password"}, contents);
+  await SyncTestingInfrastructure(server);
+
+  let user = server.user("foo");
+
+  let initialID = Service.clientsEngine.localID;
+  let remoteID = Utils.makeGUID();
+  try {
+
+    _("Syncing to initialize crypto etc.");
+    Service.sync();
+
+    _("Create remote client record");
+    server.insertWBO("foo", "clients", new ServerWBO(remoteID, encryptPayload({
+      id: remoteID,
+      name: "Remote client",
+      type: "desktop",
+      commands: [],
+      version: "54",
+      protocols: ["1.5"],
+    }), Date.now() / 1000));
+
+    let bookmarkInfo = await PlacesUtils.bookmarks.insert({
+      parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+      url: "http://getfirefox.com/",
+      title: "Get Firefox!",
+    });
+
+    let validationPromise = promiseValidationDone([]);
+    _("Syncing.");
+    Service.sync();
+    // should have 2 clients
+    equal(clientsEngine.stats.numClients, 2)
+    await validationPromise;
+
+    // Delete the bookmark localy, but cheat by telling places that Sync did
+    // it, so Sync still thinks we have it.
+    await PlacesUtils.bookmarks.remove(bookmarkInfo.guid, {
+      source: PlacesUtils.bookmarks.SOURCE_SYNC,
+    });
+    // sanity check we aren't going to sync this removal.
+    do_check_empty(bookmarksEngine.pullNewChanges());
+    // sanity check that the bookmark is not there anymore
+    do_check_false(await PlacesUtils.bookmarks.fetch(bookmarkInfo.guid));
+
+    // sync again - we should have a few problems...
+    _("Syncing again.");
+    validationPromise = promiseValidationDone([
+      {"name":"clientMissing","count":1},
+      {"name":"structuralDifferences","count":1},
+    ]);
+    Service.sync();
+    await validationPromise;
+
+    // We shouldn't have started a repair with our second client.
+    equal(clientsEngine.getClientCommands(remoteID).length, 0);
+
+    // Trigger a sync (will request the missing item)
+    Service.sync();
+
+    // And we got our bookmark back
+    do_check_true(await PlacesUtils.bookmarks.fetch(bookmarkInfo.guid));
+  } finally {
+    await cleanup(server);
   }
 });
+
+add_task(async function test_repair_server_missing() {
+  enableValidationPrefs();
+
+  _("Ensure that a record missing from the server only will get re-upload from the client");
+
+  let contents = {
+    meta: {
+      global: {
+        engines: {
+          clients: {
+            version: clientsEngine.version,
+            syncID: clientsEngine.syncID,
+          },
+          bookmarks: {
+            version: bookmarksEngine.version,
+            syncID: bookmarksEngine.syncID,
+          },
+        }
+      }
+    },
+    clients: {},
+    bookmarks: {},
+    crypto: {},
+  };
+  let server = serverForUsers({"foo": "password"}, contents);
+  await SyncTestingInfrastructure(server);
+
+  let user = server.user("foo");
+
+  let initialID = Service.clientsEngine.localID;
+  let remoteID = Utils.makeGUID();
+  try {
+
+    _("Syncing to initialize crypto etc.");
+    Service.sync();
+
+    _("Create remote client record");
+    server.insertWBO("foo", "clients", new ServerWBO(remoteID, encryptPayload({
+      id: remoteID,
+      name: "Remote client",
+      type: "desktop",
+      commands: [],
+      version: "54",
+      protocols: ["1.5"],
+    }), Date.now() / 1000));
+
+    let bookmarkInfo = await PlacesUtils.bookmarks.insert({
+      parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+      url: "http://getfirefox.com/",
+      title: "Get Firefox!",
+    });
+
+    let validationPromise = promiseValidationDone([]);
+    _("Syncing.");
+    Service.sync();
+    // should have 2 clients
+    equal(clientsEngine.stats.numClients, 2)
+    await validationPromise;
+
+    // Now we will reach into the server and hard-delete the bookmark
+    user.collection("bookmarks").wbo(bookmarkInfo.guid).delete();
+
+    // sync again - we should have a few problems...
+    _("Syncing again.");
+    validationPromise = promiseValidationDone([
+      {"name":"serverMissing","count":1},
+      {"name":"missingChildren","count":1},
+    ]);
+    Service.sync();
+    await validationPromise;
+
+    // We shouldn't have started a repair with our second client.
+    equal(clientsEngine.getClientCommands(remoteID).length, 0);
+
+    // Trigger a sync (will upload the missing item)
+    Service.sync();
+
+    // And the server got our bookmark back
+    do_check_true(user.collection("bookmarks").wbo(bookmarkInfo.guid));
+  } finally {
+    await cleanup(server);
+  }
+});
+
+add_task(async function test_repair_server_deleted() {
+  enableValidationPrefs();
+
+  _("Ensure that a record marked as deleted on the server but present on the client will get deleted on the client");
+
+  let contents = {
+    meta: {
+      global: {
+        engines: {
+          clients: {
+            version: clientsEngine.version,
+            syncID: clientsEngine.syncID,
+          },
+          bookmarks: {
+            version: bookmarksEngine.version,
+            syncID: bookmarksEngine.syncID,
+          },
+        }
+      }
+    },
+    clients: {},
+    bookmarks: {},
+    crypto: {},
+  };
+  let server = serverForUsers({"foo": "password"}, contents);
+  await SyncTestingInfrastructure(server);
+
+  let user = server.user("foo");
+
+  let initialID = Service.clientsEngine.localID;
+  let remoteID = Utils.makeGUID();
+  try {
+
+    _("Syncing to initialize crypto etc.");
+    Service.sync();
+
+    _("Create remote client record");
+    server.insertWBO("foo", "clients", new ServerWBO(remoteID, encryptPayload({
+      id: remoteID,
+      name: "Remote client",
+      type: "desktop",
+      commands: [],
+      version: "54",
+      protocols: ["1.5"],
+    }), Date.now() / 1000));
+
+    let bookmarkInfo = await PlacesUtils.bookmarks.insert({
+      parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+      url: "http://getfirefox.com/",
+      title: "Get Firefox!",
+    });
+
+    let validationPromise = promiseValidationDone([]);
+    _("Syncing.");
+    Service.sync();
+    // should have 2 clients
+    equal(clientsEngine.stats.numClients, 2)
+    await validationPromise;
+
+    // Now we will reach into the server and create a tombstone for that bookmark
+    server.insertWBO("foo", "bookmarks", new ServerWBO(bookmarkInfo.guid, encryptPayload({
+      id: bookmarkInfo.guid,
+      deleted: true,
+    }), Date.now() / 1000));
+
+    // sync again - we should have a few problems...
+    _("Syncing again.");
+    validationPromise = promiseValidationDone([
+      {"name":"serverDeleted","count":1},
+      {"name":"deletedChildren","count":1},
+      {"name":"orphans","count":1}
+    ]);
+    Service.sync();
+    await validationPromise;
+
+    // We shouldn't have started a repair with our second client.
+    equal(clientsEngine.getClientCommands(remoteID).length, 0);
+
+    // Trigger a sync (will upload the missing item)
+    Service.sync();
+
+    // And the client deleted our bookmark
+    do_check_true(!(await PlacesUtils.bookmarks.fetch(bookmarkInfo.guid)));
+  } finally {
+    await cleanup(server);
+  }
+});

--- a/services/sync/tests/unit/test_doctor.js
+++ b/services/sync/tests/unit/test_doctor.js
@@ -77,16 +77,19 @@ add_task(async function test_repairs_sta
     }
   }
   let requestor = {
     startRepairs(validationInfo, flowID) {
       ok(flowID, "got a flow ID");
       equal(validationInfo, problems);
       repairStarted = true;
       return true;
+    },
+    tryServerOnlyRepairs() {
+      return false;
     }
   }
   let doctor = mockDoctor({
     _getEnginesToValidate(recentlySyncedEngines) {
       deepEqual(recentlySyncedEngines, [engine]);
       return {
         "test-engine": { engine, maxRecords: -1 }
       };
@@ -105,16 +108,19 @@ add_task(async function test_repairs_sta
   ok(repairStarted);
 });
 
 add_task(async function test_repairs_advanced_daily() {
   let repairCalls = 0;
   let requestor = {
     continueRepairs() {
       repairCalls++;
+    },
+    tryServerOnlyRepairs() {
+      return false;
     }
   }
   // start now at just after REPAIR_ADVANCE_PERIOD so we do a a first one.
   let now = REPAIR_ADVANCE_PERIOD + 1;
   let doctor = mockDoctor({
     _getEnginesToValidate() {
       return {}; // no validations.
     },
@@ -156,16 +162,19 @@ add_task(async function test_repairs_ski
     name: "test-engine",
     getValidator() {
       return validator;
     }
   }
   let requestor = {
     startRepairs(validationInfo, flowID) {
       assert.ok(false, "Never should start repairs");
+    },
+    tryServerOnlyRepairs() {
+      return false;
     }
   }
   let doctor = mockDoctor({
     _getEnginesToValidate(recentlySyncedEngines) {
       deepEqual(recentlySyncedEngines, [engine]);
       return {
         "test-engine": { engine, maxRecords: -1 }
       };