--- a/toolkit/components/places/History.jsm
+++ b/toolkit/components/places/History.jsm
@@ -484,37 +484,16 @@ var clear = Task.async(function* (db) {
       END)
      WHERE frecency > 0`);
 
   // Notify frecency change observers.
   notify(observers, "onManyFrecenciesChanged");
 });
 
 /**
- * Remove a list of pages from `moz_places` by their id.
- *
- * @param db: (Sqlite connection)
- *      The database.
- * @param idList: (Array of integers)
- *      The `moz_places` identifiers for the places to remove.
- * @return (Promise)
- */
-var removePagesById = Task.async(function*(db, idList) {
-  if (idList.length == 0) {
-    return;
-  }
-  // Note, we are already in a transaction, since callers create it.
-  yield db.execute(`DELETE FROM moz_places
-                    WHERE id IN ( ${ sqlList(idList) } )`);
-  // Hosts accumulated during the places delete are updated through a trigger
-  // (see nsPlacesTriggers.h).
-  yield db.execute(`DELETE FROM moz_updatehosts_temp`);
-});
-
-/**
  * Clean up pages whose history has been modified, by either
  * removing them entirely (if they are marked for removal,
  * typically because all visits have been removed and there
  * are no more foreign keys such as bookmarks) or updating
  * their frecency (otherwise).
  *
  * @param db: (Sqlite connection)
  *      The database.
@@ -527,17 +506,35 @@ var removePagesById = Task.async(functio
  *              frecency updated.
  *          - hasForeign: (boolean) If `true`, the page has at least
  *              one foreign reference (i.e. a bookmark), so the page should
  *              be kept and its frecency updated.
  * @return (Promise)
  */
 var cleanupPages = Task.async(function*(db, pages) {
   yield invalidateFrecencies(db, pages.filter(p => p.hasForeign || p.hasVisits).map(p => p.id));
-  yield removePagesById(db, pages.filter(p => !p.hasForeign && !p.hasVisits).map(p => p.id));
+
+  let pageIdsToRemove = pages.filter(p => !p.hasForeign && !p.hasVisits).map(p => p.id);
+  if (pageIdsToRemove.length > 0) {
+    let idsList = sqlList(pageIdsToRemove);
+    // Note, we are already in a transaction, since callers create it.
+    yield db.execute(`DELETE FROM moz_places WHERE id IN ( ${ idsList } )`);
+    // Hosts accumulated during the places delete are updated through a trigger
+    // (see nsPlacesTriggers.h).
+    yield db.executeCached(`DELETE FROM moz_updatehosts_temp`);
+
+    // Expire orphans.
+    yield db.executeCached(`
+      DELETE FROM moz_favicons WHERE NOT EXISTS
+        (SELECT 1 FROM moz_places WHERE favicon_id = moz_favicons.id)`);
+    yield db.execute(`DELETE FROM moz_annos
+                      WHERE place_id IN ( ${ idsList } )`);
+    yield db.execute(`DELETE FROM moz_inputhistory
+                      WHERE place_id IN ( ${ idsList } )`);
+  }
 });
 
 /**
  * Notify observers that pages have been removed/updated.
  *
  * @param db: (Sqlite connection)
  *      The database.
  * @param pages: (Array of objects)

--- a/toolkit/components/places/tests/PlacesTestUtils.jsm
+++ b/toolkit/components/places/tests/PlacesTestUtils.jsm
@@ -115,33 +115,25 @@ this.PlacesTestUtils = Object.freeze({
    *
    * @note The result is achieved by asynchronously executing a query requiring
    *       a write lock.  Since all statements on the same connection are
    *       serialized, the end of this write operation means that all writes are
    *       complete.  Note that WAL makes so that writers don't block readers, but
    *       this is a problem only across different connections.
    */
   promiseAsyncUpdates() {
-    return new Promise(resolve => {
-      let db = PlacesUtils.history.DBConnection;
-      let begin = db.createAsyncStatement("BEGIN EXCLUSIVE");
-      begin.executeAsync();
-      begin.finalize();
-
-      let commit = db.createAsyncStatement("COMMIT");
-      commit.executeAsync({
-        handleResult: function () {},
-        handleError: function () {},
-        handleCompletion: function(aReason)
-        {
-          resolve();
-        }
-      });
-      commit.finalize();
-    });
+    return PlacesUtils.withConnectionWrapper("promiseAsyncUpdates", Task.async(function* (db) {
+      try {
+        yield db.executeCached("BEGIN EXCLUSIVE");
+        yield db.executeCached("COMMIT");
+      } catch (ex) {
+        // If we fail to start a transaction, it's because there is already one.
+        // In such a case we should not try to commit the existing transaction.
+      }
+    }));
   },
 
   /**
    * Asynchronously checks if an address is found in the database.
    * @param aURI
    *        nsIURI or address to look for.
    *
    * @return {Promise}

--- a/toolkit/components/places/tests/history/test_remove.js
+++ b/toolkit/components/places/tests/history/test_remove.js
@@ -337,11 +337,25 @@ add_task(function* test_error_cases() {
   try {
     PlacesUtils.history.remove("http://example.org/I/have/clearly/not/been/added", null);
     Assert.ok(true, "History.remove should ignore `null` as a second argument");
   } catch (ex) {
     Assert.ok(false, "History.remove should ignore `null` as a second argument");
   }
 });
 
-function run_test() {
-  run_next_test();
-}
+add_task(function* test_orphans() {
+  let uri = NetUtil.newURI("http://moz.org/");
+  yield PlacesTestUtils.addVisits({ uri });
+
+  PlacesUtils.favicons.setAndFetchFaviconForPage(
+    uri, SMALLPNG_DATA_URI, true,  PlacesUtils.favicons.FAVICON_LOAD_NON_PRIVATE,
+    null, Services.scriptSecurityManager.getSystemPrincipal());
+  PlacesUtils.annotations.setPageAnnotation(uri, "test", "restval", 0,
+                                            PlacesUtils.annotations.EXPIRE_NEVER);
+
+  yield PlacesUtils.history.remove(uri);
+  Assert.ok(!(yield PlacesTestUtils.isPageInDB(uri)), "Page should have been removed");
+  let db = yield PlacesUtils.promiseDBConnection();
+  let rows = yield db.execute(`SELECT (SELECT count(*) FROM moz_annos) +
+                                      (SELECT count(*) FROM moz_favicons) AS count`);
+  Assert.equal(rows[0].getResultByName("count"), 0, "Should not find orphans");
+});

--- a/toolkit/components/places/tests/history/test_removeVisitsByFilter.js
+++ b/toolkit/components/places/tests/history/test_removeVisitsByFilter.js
@@ -7,20 +7,18 @@
 
 Cu.importGlobalProperties(["URL"]);
 
 Cu.import("resource://gre/modules/PromiseUtils.jsm", this);
 
 add_task(function* test_removeVisitsByFilter() {
   let referenceDate = new Date(1999, 9, 9, 9, 9);
 
-  /**
-   * Populate a database with 20 entries, remove a subset of entries,
-   * ensure consistency.
-   */
+  // Populate a database with 20 entries, remove a subset of entries,
+  // ensure consistency.
   let remover = Task.async(function*(options) {
     do_print("Remover with options " + JSON.stringify(options));
     let SAMPLE_SIZE = options.sampleSize;
 
     yield PlacesTestUtils.clearHistory();
     yield PlacesUtils.bookmarks.eraseEverything();
 
     // Populate the database.
@@ -252,12 +250,26 @@ add_task(function* test_error_cases() {
     /TypeError: Invalid function/
   );
   Assert.throws(
     () => PlacesUtils.history.removeVisitsByFilter({beginDate: new Date(1000), endDate: new Date(0)}),
     /TypeError: `beginDate` should be at least as old/
   );
 });
 
+add_task(function* test_orphans() {
+  let uri = NetUtil.newURI("http://moz.org/");
+  yield PlacesTestUtils.addVisits({ uri });
 
-function run_test() {
-  run_next_test();
-}
+  PlacesUtils.favicons.setAndFetchFaviconForPage(
+    uri, SMALLPNG_DATA_URI, true,  PlacesUtils.favicons.FAVICON_LOAD_NON_PRIVATE,
+    null, Services.scriptSecurityManager.getSystemPrincipal());
+  PlacesUtils.annotations.setPageAnnotation(uri, "test", "restval", 0,
+                                            PlacesUtils.annotations.EXPIRE_NEVER);
+
+  yield PlacesUtils.history.removeVisitsByFilter({ beginDate: new Date(1999, 9, 9, 9, 9),
+                                                   endDate: new Date() });
+  Assert.ok(!(yield PlacesTestUtils.isPageInDB(uri)), "Page should have been removed");
+  let db = yield PlacesUtils.promiseDBConnection();
+  let rows = yield db.execute(`SELECT (SELECT count(*) FROM moz_annos) +
+                                      (SELECT count(*) FROM moz_favicons) AS count`);
+  Assert.equal(rows[0].getResultByName("count"), 0, "Should not find orphans");
+});