Index: /trunk/src/org/openstreetmap/josm/command/DeleteCommand.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/command/DeleteCommand.java	(revision 2172)
+++ /trunk/src/org/openstreetmap/josm/command/DeleteCommand.java	(revision 2173)
@@ -109,7 +109,7 @@
             String msg = "";
             switch(OsmPrimitiveType.from(primitive)) {
-            case NODE: msg = "Delete node {0}"; break;
-            case WAY: msg = "Delete way {0}"; break;
-            case RELATION:msg = "Delete relation {0}"; break;
+                case NODE: msg = "Delete node {0}"; break;
+                case WAY: msg = "Delete way {0}"; break;
+                case RELATION:msg = "Delete relation {0}"; break;
             }
 
@@ -130,7 +130,7 @@
             apiname = t.getAPIName();
             switch(t) {
-            case NODE: msg = trn("Delete {0} node", "Delete {0} nodes", toDelete.size(), toDelete.size()); break;
-            case WAY: msg = trn("Delete {0} way", "Delete {0} ways", toDelete.size(), toDelete.size()); break;
-            case RELATION: msg = trn("Delete {0} relation", "Delete {0} relations", toDelete.size(), toDelete.size()); break;
+                case NODE: msg = trn("Delete {0} node", "Delete {0} nodes", toDelete.size(), toDelete.size()); break;
+                case WAY: msg = trn("Delete {0} way", "Delete {0} ways", toDelete.size(), toDelete.size()); break;
+                case RELATION: msg = trn("Delete {0} relation", "Delete {0} relations", toDelete.size(), toDelete.size()); break;
             }
         }
@@ -231,5 +231,5 @@
      * <ul>
      *    <li>it is untagged (see {@see Node#isTagged()}</li>
-     *    <li>it is not referred to by other primitives outside of  <code>primitivesToDelete</code></li>
+     *    <li>it is not referred to by other non-deleted primitives outside of  <code>primitivesToDelete</code></li>
      * <ul>
      * @param layer  the layer in whose context primitives are deleted
@@ -251,6 +251,13 @@
                 v.initialize();
                 n.visit(v);
-                v.getData().removeAll(primitivesToDelete);
-                if (v.getData().isEmpty()) {
+                Collection<OsmPrimitive> referringPrimitives = v.getData();
+                referringPrimitives.removeAll(primitivesToDelete);
+                int count = 0;
+                for (OsmPrimitive p : referringPrimitives) {
+                    if (!p.isDeleted()) {
+                        count++;
+                    }
+                }
+                if (count == 0) {
                     nodesToDelete.add(n);
                 }