Index: /trunk/src/org/openstreetmap/josm/gui/dialogs/properties/PropertiesDialog.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/gui/dialogs/properties/PropertiesDialog.java	(revision 9761)
+++ /trunk/src/org/openstreetmap/josm/gui/dialogs/properties/PropertiesDialog.java	(revision 9762)
@@ -1370,21 +1370,30 @@
             if (sel.isEmpty())
                 return;
-            String sep = "";
-            StringBuilder s = new StringBuilder();
-            for (OsmPrimitive p : sel) {
-                String val = p.get(key);
-                if (val == null) {
-                    continue;
-                }
-                String t = "";
-                if (!sameType) {
-                    t = "";
-                } else if (p instanceof Node) {
-                    t = "type:node ";
-                } else if (p instanceof Way) {
-                    t = "type:way ";
-                } else if (p instanceof Relation) {
-                    t = "type:relation ";
-                }
+            final SearchSetting ss = createSearchSetting(key, sel, sameType);
+            org.openstreetmap.josm.actions.search.SearchAction.searchWithoutHistory(ss);
+        }
+    }
+
+    static SearchSetting createSearchSetting(String key, Collection<OsmPrimitive> sel, boolean sameType) {
+        String sep = "";
+        StringBuilder s = new StringBuilder();
+        Set<String> consideredTokens = new TreeSet<>();
+        for (OsmPrimitive p : sel) {
+            String val = p.get(key);
+            if (val == null || (!sameType && consideredTokens.contains(val))) {
+                continue;
+            }
+            String t = "";
+            if (!sameType) {
+                t = "";
+            } else if (p instanceof Node) {
+                t = "type:node ";
+            } else if (p instanceof Way) {
+                t = "type:way ";
+            } else if (p instanceof Relation) {
+                t = "type:relation ";
+            }
+            String token = new StringBuilder(t).append(val).toString();
+            if (consideredTokens.add(token)) {
                 s.append(sep).append('(').append(t).append('"').append(
                         org.openstreetmap.josm.actions.search.SearchAction.escapeStringForSearch(key)).append("\"=\"").append(
@@ -1392,10 +1401,10 @@
                 sep = " OR ";
             }
-
-            final SearchSetting ss = new SearchSetting();
-            ss.text = s.toString();
-            ss.caseSensitive = true;
-            org.openstreetmap.josm.actions.search.SearchAction.searchWithoutHistory(ss);
-        }
+        }
+
+        final SearchSetting ss = new SearchSetting();
+        ss.text = s.toString();
+        ss.caseSensitive = true;
+        return ss;
     }
 
Index: /trunk/test/unit/org/openstreetmap/josm/gui/dialogs/properties/PropertiesDialogTest.java
===================================================================
--- /trunk/test/unit/org/openstreetmap/josm/gui/dialogs/properties/PropertiesDialogTest.java	(revision 9762)
+++ /trunk/test/unit/org/openstreetmap/josm/gui/dialogs/properties/PropertiesDialogTest.java	(revision 9762)
@@ -0,0 +1,60 @@
+// License: GPL. For details, see LICENSE file.
+package org.openstreetmap.josm.gui.dialogs.properties;
+
+import static org.junit.Assert.assertEquals;
+
+import org.junit.BeforeClass;
+import org.junit.Test;
+import org.openstreetmap.josm.JOSMFixture;
+import org.openstreetmap.josm.data.coor.LatLon;
+import org.openstreetmap.josm.data.osm.DataSet;
+import org.openstreetmap.josm.data.osm.Node;
+import org.openstreetmap.josm.data.osm.Way;
+
+/**
+ * Unit tests of {@link PropertiesDialog} class.
+ */
+public class PropertiesDialogTest {
+
+    /**
+     * Setup tests
+     */
+    @BeforeClass
+    public static void setUpBeforeClass() {
+        JOSMFixture.createUnitTestFixture().init();
+    }
+
+    /**
+     * Non-regression test for ticket <a href="https://josm.openstreetmap.de/ticket/12504">#12504</a>.
+     */
+    @Test
+    public void testTicket12504() {
+        DataSet ds = new DataSet();
+        // 160 objects with foo=bar, 400 objects without foo
+        for (int i = 0; i < 160+400; i++) {
+            Node n = new Node(LatLon.ZERO);
+            if (i < 160) {
+                n.put("foo", "bar");
+            }
+            ds.addPrimitive(n);
+        }
+        assertEquals("(\"foo\"=\"bar\")",
+                PropertiesDialog.createSearchSetting("foo", ds.allPrimitives(), false).text);
+
+        Node n = new Node(LatLon.ZERO);
+        n.put("foo", "baz");
+        ds.addPrimitive(n);
+
+        assertEquals("(\"foo\"=\"bar\") OR (\"foo\"=\"baz\")",
+                PropertiesDialog.createSearchSetting("foo", ds.allPrimitives(), false).text);
+
+        ds.removePrimitive(n);
+
+        Way w = new Way();
+        w.put("foo", "bar");
+        ds.addPrimitive(w);
+
+        assertEquals("(type:node \"foo\"=\"bar\") OR (type:way \"foo\"=\"bar\")",
+                PropertiesDialog.createSearchSetting("foo", ds.allPrimitives(), true).text);
+    }
+}