Index: /trunk/src/org/openstreetmap/josm/actions/search/SearchAction.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/actions/search/SearchAction.java	(revision 11445)
+++ /trunk/src/org/openstreetmap/josm/actions/search/SearchAction.java	(revision 11446)
@@ -462,5 +462,6 @@
                 .addKeyword("new", "new ", tr("all new objects"))
                 .addKeyword("selected", "selected ", tr("all selected objects"))
-                .addKeyword("incomplete", "incomplete ", tr("all incomplete objects")),
+                .addKeyword("incomplete", "incomplete ", tr("all incomplete objects"))
+                .addKeyword("deleted", "deleted ", tr("all deleted objects (checkbox <b>{0}</b> must be enabled)", tr("all objects"))),
                 GBC.eol());
             right.add(new SearchKeywordRow(hcbSearchString)
Index: /trunk/src/org/openstreetmap/josm/actions/search/SearchCompiler.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/actions/search/SearchCompiler.java	(revision 11445)
+++ /trunk/src/org/openstreetmap/josm/actions/search/SearchCompiler.java	(revision 11446)
@@ -112,5 +112,5 @@
     public class CoreSimpleMatchFactory implements SimpleMatchFactory {
         private final Collection<String> keywords = Arrays.asList("id", "version", "type", "user", "role",
-                "changeset", "nodes", "ways", "tags", "areasize", "waylength", "modified", "selected",
+                "changeset", "nodes", "ways", "tags", "areasize", "waylength", "modified", "deleted", "selected",
                 "incomplete", "untagged", "closed", "new", "indownloadedarea",
                 "allindownloadedarea", "inview", "allinview", "timestamp", "nth", "nth%", "hasRole");
@@ -121,4 +121,6 @@
             case "modified":
                 return new Modified();
+            case "deleted":
+                return new Deleted();
             case "selected":
                 return new Selected();
@@ -1256,4 +1258,19 @@
 
     /**
+     * Matches all objects that have been deleted
+     */
+    private static class Deleted extends Match {
+        @Override
+        public boolean match(OsmPrimitive osm) {
+            return osm.isDeleted();
+        }
+
+        @Override
+        public String toString() {
+            return "deleted";
+        }
+    }
+
+    /**
      * Matches all objects currently selected
      */