diff --git a/mercurial/discovery.py b/mercurial/discovery.py
--- a/mercurial/discovery.py
+++ b/mercurial/discovery.py
@@ -271,19 +271,19 @@ def checkheads(repo, remote, outgoing, r
             # Maybe we should abort if we push more that one head
             # for new branches ?
             continue
-        if heads[2]:
-            unsynced = True
-        oldhs = set(heads[0])
         candidate_newhs = set(heads[1])
         # add unsynced data
+        oldhs = set(heads[0])
         oldhs.update(heads[2])
         candidate_newhs.update(heads[2])
         dhs = None
+        discardedheads = set()
         if repo.obsstore:
             # remove future heads which are actually obsolete by another
             # pushed element:
             #
-            # XXX There is several case this case does not handle properly
+            # XXX as above, There are several cases this case does not handle
+            # XXX properly
             #
             # (1) if <nh> is public, it won't be affected by obsolete marker
             #     and a new is created
@@ -300,11 +300,14 @@ def checkheads(repo, remote, outgoing, r
                 else:
                     for suc in obsolete.anysuccessors(repo.obsstore, nh):
                         if suc != nh and suc in allfuturecommon:
+                            discardedheads.add(nh)
                             break
                     else:
                         newhs.add(nh)
         else:
             newhs = candidate_newhs
+        if [h for h in heads[2] if h not in discardedheads]:
+            unsynced = True
         if len(newhs) > len(oldhs):
             # strip updates to existing remote heads from the new heads list
             dhs = list(newhs - bookmarkedheads - oldhs)
diff --git a/tests/test-obsolete-checkheads.t b/tests/test-obsolete-checkheads.t
--- a/tests/test-obsolete-checkheads.t
+++ b/tests/test-obsolete-checkheads.t
@@ -266,7 +266,6 @@ handled yet.
   $ hg push --traceback
   pushing to $TESTTMP/remote
   searching for changes
-  note: unsynced remote changes!
   adding changesets
   adding manifests
   adding file changes