--- a/services/sync/modules/engines.js
+++ b/services/sync/modules/engines.js
@@ -411,16 +411,25 @@ Engine.prototype = {
     this._notify("wipe-client", this.name, this._wipeClient)();
   }
 };
 
 function SyncEngine(name) {
   Engine.call(this, name || "SyncEngine");
   this.loadToFetch();
 }
+
+// Enumeration to define approaches to handling bad records.
+// Attached to the constructor to allow use as a kind of static enumeration.
+SyncEngine.kRecoveryStrategy = {
+  ignore: "ignore",
+  retry:  "retry",
+  error:  "error"
+};
+
 SyncEngine.prototype = {
   __proto__: Engine.prototype,
   _recordObj: CryptoWrapper,
   version: 1,
   downloadLimit: null,
   applyIncomingBatchSize: DEFAULT_STORE_BATCH_SIZE,
 
   get storageURL() Svc.Prefs.get("clusterURL") + Svc.Prefs.get("storageAPI") +
@@ -635,24 +644,47 @@ SyncEngine.prototype = {
       item.collection = self.name;
       
       // Remember which records were processed
       handled.push(item.id);
 
       try {
         try {
           item.decrypt();
-        } catch (ex if (Utils.isHMACMismatch(ex) &&
-                        self.handleHMACMismatch(item))) {
-          // Let's try handling it.
-          // If the callback returns true, try decrypting again, because
-          // we've got new keys.
-          self._log.info("Trying decrypt again...");
-          item.decrypt();
-        }       
+        } catch (ex if Utils.isHMACMismatch(ex)) {
+          let strategy = self.handleHMACMismatch(item, true);
+          if (strategy == SyncEngine.kRecoveryStrategy.retry) {
+            // You only get one retry.
+            try {
+              // Try decrypting again, typically because we've got new keys.
+              self._log.info("Trying decrypt again...");
+              item.decrypt();
+              strategy = null;
+            } catch (ex if Utils.isHMACMismatch(ex)) {
+              strategy = self.handleHMACMismatch(item, false);
+            }
+          }
+          
+          switch (strategy) {
+            case null:
+              // Retry succeeded! No further handling.
+              break;
+            case SyncEngine.kRecoveryStrategy.retry:
+              self._log.debug("Ignoring second retry suggestion.");
+              // Fall through to error case.
+            case SyncEngine.kRecoveryStrategy.error:
+              self._log.warn("Error decrypting record: " + Utils.exceptionStr(ex));
+              failed.push(item.id);
+              return;
+            case SyncEngine.kRecoveryStrategy.ignore:
+              self._log.debug("Ignoring record " + item.id +
+                              " with bad HMAC: already handled.");
+              return;
+          }
+        }
       } catch (ex) {
         self._log.warn("Error decrypting record: " + Utils.exceptionStr(ex));
         failed.push(item.id);
         return;
       }
 
       let shouldApply;
       try {
@@ -1002,13 +1034,32 @@ SyncEngine.prototype = {
     this.resetLastSync();
     this.toFetch = [];
   },
 
   wipeServer: function wipeServer() {
     new Resource(this.engineURL).delete();
     this._resetClient();
   },
-  
-  handleHMACMismatch: function handleHMACMismatch(item) {
-    return Weave.Service.handleHMACEvent();
+
+  /*
+   * Decide on (and partially effect) an error-handling strategy.
+   *
+   * Asks the Service to respond to an HMAC error, which might result in keys
+   * being downloaded. That call returns true if an action which might allow a
+   * retry to occur.
+   *
+   * If `mayRetry` is truthy, and the Service suggests a retry,
+   * handleHMACMismatch returns kRecoveryStrategy.retry. Otherwise, it returns
+   * kRecoveryStrategy.error.
+   *
+   * Subclasses of SyncEngine can override this method to allow for different
+   * behavior -- e.g., to delete and ignore erroneous entries.
+   *
+   * All return values will be part of the kRecoveryStrategy enumeration.
+   */
+  handleHMACMismatch: function handleHMACMismatch(item, mayRetry) {
+    // By default we either try again, or bail out noisily.
+    return (Weave.Service.handleHMACEvent() && mayRetry) ?
+           SyncEngine.kRecoveryStrategy.retry :
+           SyncEngine.kRecoveryStrategy.error;
   }
 };

--- a/services/sync/modules/engines/clients.js
+++ b/services/sync/modules/engines/clients.js
@@ -190,27 +190,29 @@ ClientEngine.prototype = {
   _resetClient: function _resetClient() this._wipeClient(),
 
   _wipeClient: function _wipeClient() {
     SyncEngine.prototype._resetClient.call(this);
     this._store.wipe();
   },
   
   // Override the default behavior to delete bad records from the server.
-  handleHMACMismatch: function handleHMACMismatch(item) {
+  handleHMACMismatch: function handleHMACMismatch(item, mayRetry) {
     this._log.debug("Handling HMAC mismatch for " + item.id);
-    if (SyncEngine.prototype.handleHMACMismatch.call(this, item))
-      return true;
+    
+    let base = SyncEngine.prototype.handleHMACMismatch.call(this, item, mayRetry);
+    if (base != SyncEngine.kRecoveryStrategy.error)
+      return base;
 
     // It's a bad client record. Save it to be deleted at the end of the sync.
     this._log.debug("Bad client record detected. Scheduling for deletion.");
     this._deleteId(item.id);
 
-    // Don't try again.
-    return false;
+    // Neither try again nor error; we're going to delete it.
+    return SyncEngine.kRecoveryStrategy.ignore;
   }
 };
 
 function ClientStore(name) {
   Store.call(this, name);
 }
 ClientStore.prototype = {
   __proto__: Store.prototype,

--- a/services/sync/tests/unit/test_clients_engine.js
+++ b/services/sync/tests/unit/test_clients_engine.js
@@ -1,12 +1,13 @@
 Cu.import("resource://services-sync/constants.js");
 Cu.import("resource://services-sync/record.js");
 Cu.import("resource://services-sync/identity.js");
 Cu.import("resource://services-sync/util.js");
+Cu.import("resource://services-sync/engines.js");
 Cu.import("resource://services-sync/engines/clients.js");
 Cu.import("resource://services-sync/service.js");
 
 const MORE_THAN_CLIENTS_TTL_REFRESH = 691200; // 8 days
 const LESS_THAN_CLIENTS_TTL_REFRESH = 86400; // 1 day
 
 function test_bad_hmac() {
   _("Ensure that Clients engine deletes corrupt records.");
@@ -71,16 +72,71 @@ function test_bad_hmac() {
     do_check_true(!deleted);
     Clients.sync();
 
     _("Old record was deleted, new one uploaded.");
     do_check_true(deleted);
     do_check_eq(1, clientsColl.count());
     _("Records now: " + clientsColl.get({}));
 
+    _("Now change our keys but don't upload them. " +
+      "That means we get an HMAC error but redownload keys.");
+    Service.lastHMACEvent = 0;
+    Clients.localID = Utils.makeGUID();
+    Clients.resetClient();
+    CollectionKeys.generateNewKeys();
+    deleted = false;
+    do_check_eq(1, clientsColl.count());
+    Clients.sync();
+
+    _("Old record was not deleted, new one uploaded.");
+    do_check_false(deleted);
+    do_check_eq(2, clientsColl.count());
+    _("Records now: " + clientsColl.get({}));
+
+    _("Now try the scenario where our keys are wrong *and* there's a bad record.");
+    // Clean up and start fresh.
+    clientsColl.wbos = {};
+    Service.lastHMACEvent = 0;
+    Clients.localID = Utils.makeGUID();
+    Clients.resetClient();
+    deleted = false;
+    do_check_eq(0, clientsColl.count());
+
+    // Create and upload keys.
+    CollectionKeys.generateNewKeys();
+    serverKeys = CollectionKeys.asWBO("crypto", "keys");
+    serverKeys.encrypt(Weave.Service.syncKeyBundle);
+    do_check_true(serverKeys.upload(Weave.Service.cryptoKeysURL).success);
+
+    // Sync once to upload a record.
+    Clients.sync();
+    do_check_eq(1, clientsColl.count());
+
+    // Generate and upload new keys, so the old client record is wrong.
+    CollectionKeys.generateNewKeys();
+    serverKeys = CollectionKeys.asWBO("crypto", "keys");
+    serverKeys.encrypt(Weave.Service.syncKeyBundle);
+    do_check_true(serverKeys.upload(Weave.Service.cryptoKeysURL).success);
+
+    // Create a new client record and new keys. Now our keys are wrong, as well
+    // as the object on the server. We'll download the new keys and also delete
+    // the bad client record.
+    Clients.localID = Utils.makeGUID();
+    Clients.resetClient();
+    CollectionKeys.generateNewKeys();
+    let oldKey = CollectionKeys.keyForCollection();
+
+    do_check_false(deleted);
+    Clients.sync();
+    do_check_true(deleted);
+    do_check_eq(1, clientsColl.count());
+    let newKey = CollectionKeys.keyForCollection();
+    do_check_false(oldKey.equals(newKey));
+
   } finally {
     server.stop(do_test_finished);
     Svc.Prefs.resetBranch("");
     Records.clearCache();
   }
 }
 
 function test_properties() {