diff -r 6de8cd5c719a -r 1b70e5941ad7 mercurial/scmutil.py
--- a/mercurial/scmutil.py	Tue Apr 02 14:49:34 2013 -0700
+++ b/mercurial/scmutil.py	Tue Apr 02 10:56:24 2013 -0700
@@ -683,19 +683,26 @@
         dstate = dirstate[abs]
         if dstate == '?' and audit_path.check(abs):
             unknown.append(abs)
-            if repo.ui.verbose or not m.exact(abs):
-                rel = m.rel(abs)
-                repo.ui.status(_('adding %s\n') % ((pats and rel) or abs))
         elif dstate != 'r' and not st:
             deleted.append(abs)
-            if repo.ui.verbose or not m.exact(abs):
-                rel = m.rel(abs)
-                repo.ui.status(_('removing %s\n') % ((pats and rel) or abs))
         # for finding renames
         elif dstate == 'r':
             removed.append(abs)
         elif dstate == 'a':
             added.append(abs)
+
+    unknownset = set(unknown)
+    toprint = unknownset.copy()
+    toprint.update(deleted)
+    for abs in sorted(toprint):
+        if repo.ui.verbose or not m.exact(abs):
+            rel = m.rel(abs)
+            if abs in unknownset:
+                status = _('adding %s\n') % ((pats and rel) or abs)
+            else:
+                status = _('removing %s\n') % ((pats and rel) or abs)
+            repo.ui.status(status)
+
     copies = {}
     if similarity > 0:
         for old, new, score in similar.findrenames(repo,