Index: /trunk/src/org/openstreetmap/josm/gui/mappaint/mapcss/MapCSSRuleIndex.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/gui/mappaint/mapcss/MapCSSRuleIndex.java	(revision 18450)
+++ /trunk/src/org/openstreetmap/josm/gui/mappaint/mapcss/MapCSSRuleIndex.java	(revision 18451)
@@ -5,4 +5,5 @@
 import java.util.BitSet;
 import java.util.Collections;
+import java.util.EnumSet;
 import java.util.HashMap;
 import java.util.Iterator;
@@ -121,4 +122,8 @@
     }
 
+    /** Valid key types for indexing (see {@link ConditionFactory.KeyMatchType}) */
+    private static final EnumSet<ConditionFactory.KeyMatchType> VALID_INDEX_KEY_TYPES = EnumSet.of(
+            ConditionFactory.KeyMatchType.EQ, ConditionFactory.KeyMatchType.TRUE, ConditionFactory.KeyMatchType.FALSE);
+
     /**
      * All rules this index is for. Once this index is built, this list is sorted.
@@ -187,5 +192,5 @@
         String key = null;
         for (Condition c : conds) {
-            if (c instanceof KeyCondition) {
+            if (c instanceof KeyCondition && VALID_INDEX_KEY_TYPES.contains(((KeyCondition) c).matchType)) {
                 KeyCondition keyCondition = (KeyCondition) c;
                 if (!keyCondition.negateResult) {
Index: /trunk/test/unit/org/openstreetmap/josm/gui/mappaint/mapcss/KeyConditionTest.java
===================================================================
--- /trunk/test/unit/org/openstreetmap/josm/gui/mappaint/mapcss/KeyConditionTest.java	(revision 18450)
+++ /trunk/test/unit/org/openstreetmap/josm/gui/mappaint/mapcss/KeyConditionTest.java	(revision 18451)
@@ -7,7 +7,18 @@
 import static org.junit.jupiter.api.Assertions.fail;
 
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.EnumSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.regex.Pattern;
+
 import org.junit.jupiter.api.BeforeEach;
 import org.junit.jupiter.api.Test;
 import org.junit.jupiter.api.extension.RegisterExtension;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.EnumSource;
+import org.openstreetmap.josm.TestUtils;
 import org.openstreetmap.josm.data.coor.LatLon;
 import org.openstreetmap.josm.data.osm.DataSet;
@@ -17,4 +28,5 @@
 import org.openstreetmap.josm.data.osm.RelationMember;
 import org.openstreetmap.josm.gui.mappaint.Environment;
+import org.openstreetmap.josm.gui.mappaint.Range;
 import org.openstreetmap.josm.gui.mappaint.mapcss.Condition.Context;
 import org.openstreetmap.josm.gui.mappaint.mapcss.ConditionFactory.KeyCondition;
@@ -149,3 +161,41 @@
         assertTrue(cond.applies(e));
     }
+
+    /**
+     * Ensure that we are accounting for all necessary {@link ConditionFactory.KeyMatchType} are accounted for.
+     * If this fails, and the key should not be fully matched against (i.e., it is a regex), please modify
+     * {@link MapCSSRuleIndex#findAnyRequiredKey}.
+     *
+     * Non-regression test for JOSM #22073.
+     */
+    @ParameterizedTest
+    @EnumSource(ConditionFactory.KeyMatchType.class)
+    void testNonRegression22073(final KeyMatchType keyMatchType) {
+        final EnumSet<ConditionFactory.KeyMatchType> current = EnumSet.of(KeyMatchType.EQ, KeyMatchType.FALSE, KeyMatchType.TRUE,
+                KeyMatchType.REGEX, KeyMatchType.ANY_CONTAINS, KeyMatchType.ANY_ENDS_WITH, KeyMatchType.ANY_STARTS_WITH);
+        assertTrue(current.contains(keyMatchType), "Is this type supposed to be matched against a whole key?");
+
+        final boolean fullKey = EnumSet.of(KeyMatchType.EQ, KeyMatchType.TRUE, KeyMatchType.FALSE).contains(keyMatchType);
+        final MapCSSRuleIndex index = new MapCSSRuleIndex();
+        final Condition condition = keyMatchType != KeyMatchType.REGEX
+                ? new KeyCondition("highway", false, keyMatchType)
+                : new ConditionFactory.KeyRegexpCondition(Pattern.compile("highway"), false);
+        index.add(new MapCSSRule(Collections.singletonList(new Selector.GeneralSelector("*", Range.ZERO_TO_INFINITY,
+                Collections.singletonList(condition), null)), null));
+        index.initIndex();
+        final Node testNode = TestUtils.newNode("highway=traffic_calming");
+        // First get all the "remaining" candidates by passing a non-tagged node
+        final Collection<MapCSSRule> remaining = convertIterator(index.getRuleCandidates(new Node(LatLon.ZERO)));
+        // Then get all the matches for the test node
+        final Collection<MapCSSRule> matches = convertIterator(index.getRuleCandidates(testNode));
+        // Finally, remove the remaining rules from the matches
+        matches.removeIf(remaining::contains);
+        assertEquals(fullKey, !matches.isEmpty());
+    }
+
+    private static <T> Collection<T> convertIterator(Iterator<T> iterator) {
+        final List<T> rList = new ArrayList<>();
+        iterator.forEachRemaining(rList::add);
+        return rList;
+    }
 }