Index: trunk/src/org/openstreetmap/josm/data/osm/DataSet.java
===================================================================
--- trunk/src/org/openstreetmap/josm/data/osm/DataSet.java	(revision 12070)
+++ trunk/src/org/openstreetmap/josm/data/osm/DataSet.java	(revision 12071)
@@ -575,8 +575,23 @@
             if (primitive == null)
                 return;
-            clearSelection(primitiveId);
-            super.removePrimitive(primitive);
-            allPrimitives.remove(primitive);
-            primitive.setDataset(null);
+            removePrimitiveImpl(primitive);
+            firePrimitivesRemoved(Collections.singletonList(primitive), false);
+        } finally {
+            endUpdate();
+        }
+    }
+
+    private void removePrimitiveImpl(OsmPrimitive primitive) {
+        clearSelection(primitive.getPrimitiveId());
+        super.removePrimitive(primitive);
+        allPrimitives.remove(primitive);
+        primitive.setDataset(null);
+    }
+
+    @Override
+    protected void removePrimitive(OsmPrimitive primitive) {
+        beginUpdate();
+        try {
+            removePrimitiveImpl(primitive);
             firePrimitivesRemoved(Collections.singletonList(primitive), false);
         } finally {
@@ -1253,9 +1268,8 @@
                     primitive -> primitive.isDeleted() && (!primitive.isVisible() || primitive.isNew()));
             if (!toCleanUp.isEmpty()) {
+                // We unselect them in advance to not fire a selection change for every primitive
                 clearSelection(toCleanUp.stream().map(OsmPrimitive::getPrimitiveId));
                 for (OsmPrimitive primitive : toCleanUp) {
-                    allPrimitives.remove(primitive);
-                    removePrimitive(primitive);
-                    primitive.setDataset(null);
+                    removePrimitiveImpl(primitive);
                 }
                 firePrimitivesRemoved(toCleanUp, false);