--- a/services/sync/modules/doctor.js
+++ b/services/sync/modules/doctor.js
@@ -83,17 +83,17 @@ this.Doctor = {
       } finally {
         this.lastRepairAdvance = this._now();
       }
     }
   },
 
   _getEnginesToValidate(recentlySyncedEngines) {
     let result = {};
-    for (let e of recentlySyncedEngines) {
+    for (let { engine: e, firstSync } of recentlySyncedEngines) {
       let prefPrefix = `engine.${e.name}.`;
       if (!Svc.Prefs.get(prefPrefix + "validation.enabled", false)) {
         log.info(`Skipping check of ${e.name} - disabled via preferences`);
         continue;
       }
       // Check the last validation time for the engine.
       let lastValidation = Svc.Prefs.get(prefPrefix + "validation.lastTime", 0);
       let validationInterval = Svc.Prefs.get(prefPrefix + "validation.interval");
@@ -103,24 +103,31 @@ this.Doctor = {
         log.info(`Skipping validation of ${e.name}: too recent since last validation attempt`);
         continue;
       }
       // Update the time now, even if we decline to actually perform a
       // validation. We don't want to check the rest of these more frequently
       // than once a day.
       Svc.Prefs.set("validation.lastTime", Math.floor(nowSeconds));
 
-      // Validation only occurs a certain percentage of the time.
-      let validationProbability = Svc.Prefs.get(prefPrefix + "validation.percentageChance", 0) / 100.0;
+      // Validation only occurs a certain percentage of the time, and with a
+      // maximum record threshold. The limits are different for the first
+      // sync, since it's already expensive.
+      let thresholdPrefPrefix = prefPrefix + "validation.";
+      if (firstSync) {
+        thresholdPrefPrefix += "firstSync.";
+      }
+
+      let validationProbability = Svc.Prefs.get(thresholdPrefPrefix + "percentageChance", 0) / 100.0;
       if (validationProbability < Math.random()) {
         log.info(`Skipping validation of ${e.name}: Probability threshold not met`);
         continue;
       }
 
-      let maxRecords = Svc.Prefs.get(prefPrefix + "validation.maxRecords");
+      let maxRecords = Svc.Prefs.get(thresholdPrefPrefix + "maxRecords");
       if (!maxRecords) {
         log.info(`Skipping validation of ${e.name}: No maxRecords specified`);
         continue;
       }
       // OK, so this is a candidate - the final decision will be based on the
       // number of records actually found.
       result[e.name] = { engine: e, maxRecords };
     }

--- a/services/sync/modules/stages/enginesync.js
+++ b/services/sync/modules/stages/enginesync.js
@@ -160,22 +160,23 @@ EngineSynchronizer.prototype = {
     } else {
       this._log.info("Syncing all enabled engines.");
       enginesToSync = engineManager.getEnabled();
     }
     try {
       // We don't bother validating engines that failed to sync.
       let enginesToValidate = [];
       for (let engine of enginesToSync) {
+        let firstSync = engine.lastSyncLocal === 0;
         // If there's any problems with syncing the engine, report the failure
         if (!(this._syncEngine(engine)) || this.service.status.enforceBackoff) {
           this._log.info("Aborting sync for failure in " + engine.name);
           break;
         }
-        enginesToValidate.push(engine);
+        enginesToValidate.push({ engine, firstSync });
       }
 
       // If _syncEngine fails for a 401, we might not have a cluster URL here.
       // If that's the case, break out of this immediately, rather than
       // throwing an exception when trying to fetch metaURL.
       if (!this.service.clusterURL) {
         this._log.debug("Aborting sync, no cluster URL: " +
                         "not uploading new meta/global.");
@@ -242,32 +243,34 @@ EngineSynchronizer.prototype = {
   },
 
   _updateEnabledFromMeta(meta, numClients, engineManager = this.service.engineManager) {
     this._log.info("Updating enabled engines: " +
                     numClients + " clients.");
 
     if (meta.isNew || !meta.payload.engines) {
       this._log.debug("meta/global isn't new, or is missing engines. Not updating enabled state.");
+      Svc.Prefs.resetBranch("engineStatusChanged.");
       return;
     }
 
     // If we're the only client, and no engines are marked as enabled,
     // thumb our noses at the server data: it can't be right.
     // Belt-and-suspenders approach to Bug 615926.
     let hasEnabledEngines = false;
     for (let e in meta.payload.engines) {
       if (e != "clients") {
         hasEnabledEngines = true;
         break;
       }
     }
 
     if ((numClients <= 1) && !hasEnabledEngines) {
       this._log.info("One client and no enabled engines: not touching local engine status.");
+      Svc.Prefs.resetBranch("engineStatusChanged.");
       return;
     }
 
     this.service._ignorePrefObserver = true;
 
     let enabled = engineManager.enabledEngineNames;
 
     let toDecline = new Set();

--- a/services/sync/services-sync.js
+++ b/services/sync/services-sync.js
@@ -78,8 +78,11 @@ pref("services.sync.engine.bookmarks.val
 
 // We only run validation `services.sync.validation.percentageChance` percent of
 // the time, even if it's been the right amount of time since the last validation,
 // and you meet the maxRecord checks.
 pref("services.sync.engine.bookmarks.validation.percentageChance", 10);
 
 // We won't validate an engine if it has more than this many records on the server.
 pref("services.sync.engine.bookmarks.validation.maxRecords", 1000);
+
+pref("services.sync.engine.bookmarks.validation.firstSync.percentageChance", 100);
+pref("services.sync.engine.bookmarks.validation.firstSync.maxRecords", 1000);

--- a/services/sync/tests/unit/test_telemetry.js
+++ b/services/sync/tests/unit/test_telemetry.js
@@ -62,19 +62,79 @@ BogusEngine.prototype = Object.create(St
 async function cleanAndGo(engine, server) {
   engine._tracker.clearChangedIDs();
   Svc.Prefs.resetBranch("");
   Svc.Prefs.set("log.logger.engine.rotary", "Trace");
   Service.recordManager.clearCache();
   await promiseStopServer(server);
 }
 
+function getEngineValidationData(ping, name) {
+  let engine = ping.engines.find(e => e.name == name);
+  return engine ? engine.validation : null;
+}
+
 // Avoid addon manager complaining about not being initialized
 Service.engineManager.unregister("addons");
 
+add_task(async function test_validate_on_first_sync() {
+  Svc.Prefs.set("engine.bookmarks.validation.enabled", true);
+  Svc.Prefs.set("engine.bookmarks.validation.firstSync.percentageChance", 100);
+  Svc.Prefs.set("engine.bookmarks.validation.firstSync.maxRecords", -1);
+  Svc.Prefs.set("engine.bookmarks.validation.percentageChance", 0);
+  Svc.Prefs.set("engine.bookmarks.validation.maxRecords", -1);
+
+  let engine = Service.engineManager.get("bookmarks");
+  let server = serverForUsers({ foo: "password" }, {
+    meta: {
+      global: {
+        engines: {
+          bookmarks: {
+            version: engine.version,
+            syncID: engine.syncID,
+          },
+        },
+      },
+    },
+  });
+  await SyncTestingInfrastructure(server);
+
+  try {
+    _("First sync; disabled engine");
+    engine.enabled = false;
+    {
+      let ping = await sync_and_validate_telem();
+      ok(!getEngineValidationData(ping, "bookmarks"),
+        "Should not validate disabled bookmarks engine");
+    }
+    ok(!Svc.Prefs.get("engineStatusChanged.bookmarks", false),
+      "Should reset status for disabled bookmarks engine after first sync");
+
+    _("First engine sync should have validation data; chance is 100%");
+    engine.enabled = true;
+    {
+      let ping = await sync_and_validate_telem();
+      ok(getEngineValidationData(ping, "bookmarks"),
+        "Should validate on first bookmarks sync");
+    }
+    ok(!Svc.Prefs.get("engineStatusChanged.bookmarks", false),
+      "Should reset status for enabled bookmarks engine after first engine sync");
+
+    _("Second engine sync should not have validation data; chance is 0%");
+    {
+      let ping = await sync_and_validate_telem();
+      ok(!getEngineValidationData(ping, "bookmarks"),
+        "Should not validate on second bookmarks sync");
+    }
+  } finally {
+    Service.startOver();
+    await promiseStopServer(server);
+  }
+});
+
 add_task(async function test_basic() {
   let helper = track_collections_helper();
   let upd = helper.with_updated_collection;
 
   let handlers = {
     "/1.1/johndoe/info/collections": helper.handler,
     "/1.1/johndoe/storage/crypto/keys": upd("crypto", new ServerWBO("keys").handler()),
     "/1.1/johndoe/storage/meta/global": upd("meta", new ServerWBO("global").handler())