--- a/browser/components/preferences/in-content/findInPage.js
+++ b/browser/components/preferences/in-content/findInPage.js
@@ -264,29 +264,28 @@ var gSearchResultsPane = {
           if (query !== this.query) {
             return;
           }
         }
 
         if (!child.classList.contains("header") &&
             !child.classList.contains("subcategory") &&
             await this.searchWithinNode(child, this.query)) {
-          child.hidden = false;
           child.classList.remove("visually-hidden");
 
           // Show the preceding search-header if one exists.
           let groupbox = child.closest("groupbox");
           let groupHeader = groupbox && groupbox.querySelector(".search-header");
           if (groupHeader) {
             groupHeader.hidden = false;
           }
 
           resultsFound = true;
-        } else if (!child.hidden) {
-          child.hidden = true;
+        } else {
+          child.classList.add("visually-hidden");
         }
       }
 
       noResultsEl.hidden = !!resultsFound;
       noResultsEl.setAttribute("query", this.query);
       // XXX: This is potentially racy in case where Fluent retranslates the
       // message and ereases the query within.
       // The feature is not yet supported, but we should fix for it before
@@ -309,19 +308,17 @@ var gSearchResultsPane = {
     } else {
       noResultsEl.hidden = true;
       document.getElementById("sorry-message-query").textContent = "";
       // Going back to General when cleared
       gotoPref("paneGeneral");
 
       // Hide some special second level headers in normal view
       for (let element of document.querySelectorAll("caption.search-header")) {
-        if (!element.hidden) {
-          element.hidden = true;
-        }
+        element.hidden = true;
       }
     }
 
     window.dispatchEvent(new CustomEvent("PreferencesSearchCompleted", { detail: query }));
   },
 
   /**
    * Finding leaf nodes and checking their content for words to search,
@@ -511,17 +508,17 @@ var gSearchResultsPane = {
    *    Word or words that are being searched for
    */
   createSearchTooltip(anchorNode, query) {
     if (anchorNode.tooltipNode) {
       return;
     }
     let searchTooltip = anchorNode.ownerDocument.createElement("span");
     let searchTooltipText = anchorNode.ownerDocument.createElement("span");
-    searchTooltip.setAttribute("class", "search-tooltip");
+    searchTooltip.className = "search-tooltip";
     searchTooltipText.textContent = query;
     searchTooltip.appendChild(searchTooltipText);
 
     // Set tooltipNode property to track corresponded tooltip node.
     anchorNode.tooltipNode = searchTooltip;
     anchorNode.parentElement.classList.add("search-tooltip-parent");
     anchorNode.parentElement.appendChild(searchTooltip);
 
@@ -533,25 +530,21 @@ var gSearchResultsPane = {
     // In order to get the up-to-date position of each of the nodes that we're
     // putting tooltips on, we have to flush layout intentionally, and that
     // this is the result of a XUL limitation (bug 1363730).
     let tooltipRect = searchTooltip.getBoundingClientRect();
     searchTooltip.style.setProperty("left", `calc(50% - ${(tooltipRect.width / 2)}px)`);
   },
 
   /**
-   * Remove all search tooltips that were created.
+   * Remove all search tooltips.
    */
   removeAllSearchTooltips() {
-    let searchTooltips = Array.from(document.querySelectorAll(".search-tooltip"));
-    for (let searchTooltip of searchTooltips) {
-      searchTooltip.parentElement.classList.remove("search-tooltip-parent");
-      searchTooltip.remove();
-    }
     for (let anchorNode of this.listSearchTooltips) {
+      anchorNode.parentElement.classList.remove("search-tooltip-parent");
       anchorNode.tooltipNode.remove();
       anchorNode.tooltipNode = null;
     }
     this.listSearchTooltips.clear();
   },
 
   /**
    * Remove all indicators on menuitem.

--- a/browser/components/preferences/in-content/preferences.js
+++ b/browser/components/preferences/in-content/preferences.js
@@ -187,27 +187,28 @@ function gotoPref(aCategory) {
           .add(telemetryBucketForCategory(friendlyName));
 }
 
 function search(aQuery, aAttribute) {
   let mainPrefPane = document.getElementById("mainPrefPane");
   let elements = mainPrefPane.children;
   for (let element of elements) {
     // If the "data-hidden-from-search" is "true", the
-    // element will not get considered during search. This
-    // should only be used when an element is still under
-    // development and should not be shown for any reason.
+    // element will not get considered during search.
     if (element.getAttribute("data-hidden-from-search") != "true" ||
         element.getAttribute("data-subpanel") == "true") {
       let attributeValue = element.getAttribute(aAttribute);
       if (attributeValue == aQuery) {
         element.hidden = false;
       } else {
         element.hidden = true;
       }
+    } else if (element.getAttribute("data-hidden-from-search") == "true" &&
+               !element.hidden) {
+      element.hidden = true;
     }
     element.classList.remove("visually-hidden");
   }
 
   let keysets = mainPrefPane.getElementsByTagName("keyset");
   for (let element of keysets) {
     let attributeValue = element.getAttribute(aAttribute);
     if (attributeValue == aQuery)

--- a/browser/components/preferences/in-content/tests/browser.ini
+++ b/browser/components/preferences/in-content/tests/browser.ini
@@ -11,16 +11,17 @@ support-files =
 [browser_applications_selection.js]
 skip-if = os == 'linux' # bug 1382057
 [browser_advanced_update.js]
 skip-if = !updater
 [browser_basic_rebuild_fonts_test.js]
 [browser_bug410900.js]
 [browser_bug705422.js]
 [browser_bug731866.js]
+[browser_search_no_results_change_category.js]
 [browser_search_within_preferences_1.js]
 [browser_search_within_preferences_2.js]
 [browser_search_within_preferences_command.js]
 [browser_search_subdialogs_within_preferences_1.js]
 [browser_search_subdialogs_within_preferences_2.js]
 [browser_search_subdialogs_within_preferences_3.js]
 [browser_search_subdialogs_within_preferences_4.js]
 [browser_search_subdialogs_within_preferences_5.js]

new file mode 100644
--- /dev/null
+++ b/browser/components/preferences/in-content/tests/browser_search_no_results_change_category.js
@@ -0,0 +1,28 @@
+"use strict";
+
+add_task(async function() {
+  await SpecialPowers.pushPrefEnv({"set": [["browser.preferences.search", true]]});
+});
+
+add_task(async function() {
+  await openPreferencesViaOpenPreferencesAPI("paneGeneral", {leaveOpen: true});
+
+  let searchInput = gBrowser.contentDocument.getElementById("searchInput");
+  is(searchInput, gBrowser.contentDocument.activeElement.closest("#searchInput"),
+    "Search input should be focused when visiting preferences");
+  let query = "ffff____noresults____ffff";
+  let searchCompletedPromise = BrowserTestUtils.waitForEvent(
+      gBrowser.contentWindow, "PreferencesSearchCompleted", evt => evt.detail == query);
+  EventUtils.sendString(query);
+  await searchCompletedPromise;
+
+  let noResultsEl = gBrowser.contentDocument.querySelector("#no-results-message");
+  is_element_visible(noResultsEl, "Should be reporting no results for this query");
+
+  let privacyCategory = gBrowser.contentDocument.querySelector("#category-privacy");
+  privacyCategory.click();
+  is_element_hidden(noResultsEl,
+                    "Should not be showing the 'no results' message after selecting a category");
+
+  BrowserTestUtils.removeTab(gBrowser.selectedTab);
+});