--- a/toolkit/components/passwordmgr/storage-json.js
+++ b/toolkit/components/passwordmgr/storage-json.js
@@ -108,18 +108,33 @@ this.LoginManagerStorage_json.prototype 
     let [encUsername, encPassword, encType] = this._encryptLogin(login);
 
     // Clone the login, so we don't modify the caller's object.
     let loginClone = login.clone();
 
     // Initialize the nsILoginMetaInfo fields, unless the caller gave us values
     loginClone.QueryInterface(Ci.nsILoginMetaInfo);
     if (loginClone.guid) {
-      if (!this._isGuidUnique(loginClone.guid))
-        throw new Error("specified GUID already exists");
+      let guid = loginClone.guid;
+      if (!this._isGuidUnique(guid)) {
+        // We have an existing GUID, but it's possible that entry is unable
+        // to be decrypted - if that's the case we remove the existing one
+        // and allow this one to be added.
+        let existing = this._searchLogins({guid})[0];
+        if (this._decryptLogins(existing).length) {
+          // Existing item is good, so it's an error to try and re-add it.
+          throw new Error("specified GUID already exists");
+        }
+        // find and remove the existing bad entry.
+        let foundIndex = this._store.data.logins.findIndex(l => l.guid == guid);
+        if (foundIndex == -1) {
+          throw new Error("can't find a matching GUID to remove");
+        }
+        this._store.data.logins.splice(foundIndex, 1);
+      }
     } else {
       loginClone.guid = gUUIDGenerator.generateUUID().toString();
     }
 
     // Set timestamps
     let currentTime = Date.now();
     if (!loginClone.timeCreated)
       loginClone.timeCreated = currentTime;

--- a/toolkit/components/passwordmgr/test/unit/test_logins_decrypt_failure.js
+++ b/toolkit/components/passwordmgr/test/unit/test_logins_decrypt_failure.js
@@ -70,8 +70,57 @@ add_task(function test_logins_decrypt_fa
   do_check_eq(Services.logins.getAllLogins().length, 0);
   do_check_eq(Services.logins.countLogins("", "", ""), logins.length);
 
   // Removing all logins removes the non-decryptable entries also.
   Services.logins.removeAllLogins();
   do_check_eq(Services.logins.getAllLogins().length, 0);
   do_check_eq(Services.logins.countLogins("", "", ""), 0);
 });
+
+// Bug 621846 - If a login has a GUID but can't be decrypted, a search for
+// that GUID will (correctly) fail. Ensure we can add a new login with that
+// same GUID.
+add_task(function test_add_logins_with_decrypt_failure()
+{
+  // a login with a GUID.
+  let login = new LoginInfo("http://www.example2.com", "http://www.example2.com", null,
+                            "the username", "the password for www.example.com",
+                            "form_field_username", "form_field_password");
+
+  login.QueryInterface(Ci.nsILoginMetaInfo);
+  login.guid = "{4bc50d2f-dbb6-4aa3-807c-c4c2065a2c35}";
+
+  // A different login but with the same GUID.
+  let loginDupeGuid = new LoginInfo("http://www.example3.com", "http://www.example3.com", null,
+                                   "the username", "the password",
+                                   "form_field_username", "form_field_password");
+  loginDupeGuid.QueryInterface(Ci.nsILoginMetaInfo);
+  loginDupeGuid.guid = login.guid;
+
+  Services.logins.addLogin(login);
+
+  // We can search for this login by GUID.
+  let searchProp = Cc["@mozilla.org/hash-property-bag;1"]
+                   .createInstance(Ci.nsIWritablePropertyBag2);
+  searchProp.setPropertyAsAUTF8String("guid", login.guid);
+
+  equal(Services.logins.searchLogins({}, searchProp).length, 1);
+
+  // We should fail to re-add it as it remains good.
+  Assert.throws(() => Services.logins.addLogin(login),
+                /This login already exists./);
+  // We should fail to re-add a different login with the same GUID.
+  Assert.throws(() => Services.logins.addLogin(loginDupeGuid),
+                /specified GUID already exists/);
+
+  // This makes the existing login non-decryptable.
+  resetMasterPassword();
+
+  // We can no longer find it in our search.
+  equal(Services.logins.searchLogins({}, searchProp).length, 0);
+
+  // So we should be able to re-add a login with that same GUID.
+  Services.logins.addLogin(login);
+  equal(Services.logins.searchLogins({}, searchProp).length, 1);
+
+  Services.logins.removeAllLogins();
+});