--- a/services/common/utils.js
+++ b/services/common/utils.js
@@ -65,16 +65,33 @@ this.CommonUtils = {
       if (!b.has(x)) {
         return false;
       }
     }
     return true;
   },
 
   /**
+   * Checks elements in two arrays for equality, as determined by the `===`
+   * operator. This function does not perform a deep comparison; see Sync's
+   * `Util.deepEquals` for that.
+   */
+  arrayEqual(a, b) {
+    if (a.length !== b.length) {
+      return false;
+    }
+    for (let i = 0; i < a.length; i++) {
+      if (a[i] !== b[i]) {
+        return false;
+      }
+    }
+    return true;
+  },
+
+  /**
    * Encode byte string as base64URL (RFC 4648).
    *
    * @param bytes
    *        (string) Raw byte string to encode.
    * @param pad
    *        (bool) Whether to include padding characters (=). Defaults
    *        to true for historical reasons.
    */

--- a/services/sync/modules/bookmark_validator.js
+++ b/services/sync/modules/bookmark_validator.js
@@ -1,33 +1,89 @@
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this file,
  * You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 "use strict";
 
-const Cu = Components.utils;
+const { interfaces: Ci, utils: Cu } = Components;
 
 Cu.import("resource://gre/modules/PlacesUtils.jsm");
 Cu.import("resource://gre/modules/PlacesSyncUtils.jsm");
 Cu.import("resource://gre/modules/Services.jsm");
 Cu.import("resource://gre/modules/Task.jsm");
 Cu.import("resource://gre/modules/Timer.jsm");
 Cu.import("resource://gre/modules/XPCOMUtils.jsm");
+Cu.import("resource://services-common/utils.js");
+
+Cu.importGlobalProperties(["URLSearchParams"]);
 
 this.EXPORTED_SYMBOLS = ["BookmarkValidator", "BookmarkProblemData"];
 
 const LEFT_PANE_ROOT_ANNO = "PlacesOrganizer/OrganizerFolder";
 const LEFT_PANE_QUERY_ANNO = "PlacesOrganizer/OrganizerQuery";
+const QUERY_PROTOCOL = "place:";
 
 // Indicates if a local bookmark tree node should be excluded from syncing.
 function isNodeIgnored(treeNode) {
   return treeNode.annos && treeNode.annos.some(anno => anno.name == LEFT_PANE_ROOT_ANNO ||
                                                        anno.name == LEFT_PANE_QUERY_ANNO);
 }
+
+function areURLsEqual(a, b) {
+  if (a === b) {
+    return true;
+  }
+  if (a.startsWith(QUERY_PROTOCOL) != b.startsWith(QUERY_PROTOCOL)) {
+    return false;
+  }
+  // Tag queries are special because we rewrite them to point to the
+  // local tag folder ID. It's expected that the folders won't match,
+  // but all other params should.
+  let aParams = new URLSearchParams(a.slice(QUERY_PROTOCOL.length));
+  let aType = +aParams.get("type");
+  if (aType != Ci.nsINavHistoryQueryOptions.RESULTS_AS_TAG_CONTENTS) {
+    return false;
+  }
+  let bParams = new URLSearchParams(b.slice(QUERY_PROTOCOL.length));
+  let bType = +bParams.get("type");
+  if (bType != Ci.nsINavHistoryQueryOptions.RESULTS_AS_TAG_CONTENTS) {
+    return false;
+  }
+  let aKeys = new Set(aParams.keys());
+  let bKeys = new Set(bParams.keys());
+  if (aKeys.size != bKeys.size) {
+    return false;
+  }
+  // Tag queries shouldn't reference multiple folders, or named folders like
+  // "TOOLBAR" or "BOOKMARKS_MENU". Just in case, we make sure all folder IDs
+  // are numeric. If they are, we ignore them when comparing the query params.
+  if (aKeys.has("folder") && aParams.getAll("folder").every(isFinite)) {
+    aKeys.delete("folder");
+  }
+  if (bKeys.has("folder") && bParams.getAll("folder").every(isFinite)) {
+    bKeys.delete("folder");
+  }
+  for (let key of aKeys) {
+    if (!bKeys.has(key)) {
+      return false;
+    }
+    if (!CommonUtils.arrayEqual(aParams.getAll(key).sort(),
+                                bParams.getAll(key).sort())) {
+      return false;
+    }
+  }
+  for (let key of bKeys) {
+    if (!aKeys.has(key)) {
+      return false;
+    }
+  }
+  return true;
+}
+
 const BOOKMARK_VALIDATOR_VERSION = 1;
 
 /**
  * Result of bookmark validation. Contains the following fields which describe
  * server-side problems unless otherwise specified.
  *
  * - missingIDs (number): # of objects with missing ids
  * - duplicates (array of ids): ids seen more than once
@@ -163,17 +219,17 @@ XPCOMUtils.defineLazyGetter(this, "SYNCE
   PlacesUtils.bookmarks.unfiledGuid,
   PlacesUtils.bookmarks.mobileGuid,
 ]);
 
 class BookmarkValidator {
 
   _followQueries(recordMap) {
     for (let [guid, entry] of recordMap) {
-      if (entry.type !== "query" && (!entry.bmkUri || !entry.bmkUri.startsWith("place:"))) {
+      if (entry.type !== "query" && (!entry.bmkUri || !entry.bmkUri.startsWith(QUERY_PROTOCOL))) {
         continue;
       }
       // Might be worth trying to parse the place: query instead so that this
       // works "automatically" with things like aboutsync.
       let queryNodeParent = PlacesUtils.getFolderContents(entry, false, true);
       if (!queryNodeParent || !queryNodeParent.root.hasChildren) {
         continue;
       }
@@ -233,17 +289,17 @@ class BookmarkValidator {
       }
       let guid = PlacesSyncUtils.bookmarks.guidToSyncId(treeNode.guid);
       let itemType = "item";
       treeNode.ignored = !synced;
       treeNode.id = guid;
       switch (treeNode.type) {
         case PlacesUtils.TYPE_X_MOZ_PLACE:
           let query = null;
-          if (treeNode.annos && treeNode.uri.startsWith("place:")) {
+          if (treeNode.annos && treeNode.uri.startsWith(QUERY_PROTOCOL)) {
             query = treeNode.annos.find(({name}) =>
               name === PlacesSyncUtils.bookmarks.SMART_BOOKMARKS_ANNO);
           }
           if (query && query.value) {
             itemType = "query";
           } else {
             itemType = "bookmark";
           }
@@ -680,38 +736,38 @@ class BookmarkValidator {
 
       if (client.parentid || server.parentid) {
         if (client.parentid !== server.parentid) {
           structuralDifferences.push("parentid");
         }
       }
 
       if (client.tags || server.tags) {
-        let cl = client.tags || [];
-        let sl = server.tags || [];
-        if (cl.length !== sl.length || !cl.every((tag, i) => sl.indexOf(tag) >= 0)) {
+        let cl = client.tags ? [...client.tags].sort() : [];
+        let sl = server.tags ? [...server.tags].sort() : [];
+        if (!CommonUtils.arrayEqual(cl, sl)) {
           differences.push("tags");
         }
       }
 
       let sameType = client.type === server.type;
       if (!sameType) {
-        if (server.type === "query" && client.type === "bookmark" && client.bmkUri.startsWith("place:")) {
+        if (server.type === "query" && client.type === "bookmark" && client.bmkUri.startsWith(QUERY_PROTOCOL)) {
           sameType = true;
         }
       }
 
 
       if (!sameType) {
         differences.push("type");
       } else {
         switch (server.type) {
           case "bookmark":
           case "query":
-            if (server.bmkUri !== client.bmkUri) {
+            if (!areURLsEqual(server.bmkUri, client.bmkUri)) {
               differences.push("bmkUri");
             }
             break;
           case "livemark":
             if (server.feedUri != client.feedUri) {
               differences.push("feedUri");
             }
             if (server.siteUri != client.siteUri) {
@@ -722,17 +778,17 @@ class BookmarkValidator {
             if (server.id === "places" && !problemData.rootOnServer) {
               // It's the fabricated places root. It won't have the GUIDs, but
               // it doesn't matter.
               break;
             }
             if (client.childGUIDs || server.childGUIDs) {
               let cl = client.childGUIDs || [];
               let sl = server.childGUIDs || [];
-              if (cl.length !== sl.length || !cl.every((id, i) => sl[i] === id)) {
+              if (!CommonUtils.arrayEqual(cl, sl)) {
                 structuralDifferences.push("childGUIDs");
               }
             }
             break;
         }
       }
 
       if (differences.length) {

--- a/services/sync/tests/unit/test_bookmark_validator.js
+++ b/services/sync/tests/unit/test_bookmark_validator.js
@@ -226,16 +226,54 @@ add_task(async function test_cswc_differ
     server[2].type = "bookmark";
     let c = (await compareServerWithClient(server, client)).problemData;
     equal(c.clientMissing.length, 0);
     equal(c.serverMissing.length, 0);
     deepEqual(c.differences, [{id: "cccccccccccc", differences: ["type"]}]);
   }
 });
 
+add_task(async function test_cswc_differentURLs() {
+  let {server, client} = getDummyServerAndClient();
+  client.children[0].children.push({
+    guid: "dddddddddddd",
+    title: "Tag query",
+    "type": "text/x-moz-place",
+    "uri": "place:type=7&folder=80",
+  }, {
+    guid: "eeeeeeeeeeee",
+    title: "Firefox",
+    "type": "text/x-moz-place",
+    "uri": "http://getfirefox.com",
+  });
+  server.push({
+    id: "dddddddddddd",
+    parentid: "menu",
+    parentName: "foo",
+    title: "Tag query",
+    type: "query",
+    folderName: "taggy",
+    bmkUri: "place:type=7&folder=90",
+  }, {
+    id: "eeeeeeeeeeee",
+    parentid: "menu",
+    parentName: "foo",
+    title: "Firefox",
+    type: "bookmark",
+    bmkUri: "https://mozilla.org/firefox",
+  });
+
+  let c = (await compareServerWithClient(server, client)).problemData;
+  equal(c.differences.length, 1);
+  deepEqual(c.differences, [{
+    id: "eeeeeeeeeeee",
+    differences: ["bmkUri"],
+  }]);
+});
+
 add_task(async function test_cswc_serverUnexpected() {
   let {server, client} = getDummyServerAndClient();
   client.children.push({
     "guid": "dddddddddddd",
     "title": "",
     "id": 2000,
     "annos": [{
       "name": "places/excludeFromBackup",