diff --git a/mercurial/discovery.py b/mercurial/discovery.py
--- a/mercurial/discovery.py
+++ b/mercurial/discovery.py
@@ -264,6 +264,8 @@ def checkheads(repo, remote, outgoing, r
     error = None
     unsynced = False
     allmissing = set(outgoing.missing)
+    allfuturecommon = set(c.node() for c in repo.set('%ld', outgoing.common))
+    allfuturecommon.update(allmissing)
     for branch, heads in headssum.iteritems():
         if heads[0] is None:
             # Maybe we should abort if we push more that one head
@@ -293,11 +295,11 @@ def checkheads(repo, remote, outgoing, r
             # more tricky for unsynced changes.
             newhs = set()
             for nh in candidate_newhs:
-                if repo[nh].phase() <= phases.public:
+                if nh in repo and repo[nh].phase() <= phases.public:
                     newhs.add(nh)
                 else:
                     for suc in obsolete.anysuccessors(repo.obsstore, nh):
-                        if suc != nh and suc in allmissing:
+                        if suc != nh and suc in allfuturecommon:
                             break
                     else:
                         newhs.add(nh)
diff --git a/tests/test-bookmarks-pushpull.t b/tests/test-bookmarks-pushpull.t
--- a/tests/test-bookmarks-pushpull.t
+++ b/tests/test-bookmarks-pushpull.t
@@ -286,7 +286,7 @@ bookmark, not all outgoing changes:
   $ hg book -r tip add-bar
 Note: this push *must* push only a single changeset, as that's the point
 of this test.
-  $ hg push -B add-foo
+  $ hg push -B add-foo --traceback
   pushing to http://localhost:$HGPORT/
   searching for changes
   remote: adding changesets
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
@@ -159,3 +159,115 @@ Push should abort on new head
   abort: push creates new remote head d7d41ccbd4de!
   (did you forget to merge? use push -f to force)
   [255]
+
+
+
+Both precursors and successors are already know remotely. Descendant adds heads
+===============================================================================
+
+setup. (The obsolete marker is known locally only
+
+  $ cd ..
+  $ rm -rf local
+  $ hg clone remote local
+  updating to branch default
+  2 files updated, 0 files merged, 0 files removed, 0 files unresolved
+  $ cd local
+  $ mkcommit old
+  old already tracked!
+  nothing changed
+  [1]
+  $ hg up -q '.^'
+  $ mkcommit new
+  created new head
+  $ hg push -f
+  pushing to $TESTTMP/remote
+  searching for changes
+  adding changesets
+  adding manifests
+  adding file changes
+  added 1 changesets with 1 changes to 1 files (+1 heads)
+  $ mkcommit desc1
+  $ hg up -q '.^'
+  $ mkcommit desc2
+  created new head
+  $ hg debugobsolete `getid old` `getid new`
+  $ hg glog --hidden
+  @  5fe37041cc2b (draft) add desc2
+  |
+  | o  a3ef1d111c5f (draft) add desc1
+  |/
+  o  71e3228bffe1 (draft) add new
+  |
+  | x  c70b08862e08 (draft) add old
+  |/
+  o  b4952fcf48cf (public) add base
+  
+  $ hg glog --hidden -R ../remote
+  o  71e3228bffe1 (draft) add new
+  |
+  | o  c70b08862e08 (draft) add old
+  |/
+  @  b4952fcf48cf (public) add base
+  
+  $ cp -r ../remote ../backup2
+
+Push should not warn about adding new heads. We create one, but we'll delete
+one anyway.
+
+  $ hg push
+  pushing to $TESTTMP/remote
+  searching for changes
+  adding changesets
+  adding manifests
+  adding file changes
+  added 2 changesets with 2 changes to 2 files (+1 heads)
+
+
+Remote head is unknown but obsoleted by a local changeset
+=========================================================
+
+setup
+
+  $ rm -fr ../remote
+  $ cp -r ../backup1 ../remote
+  $ cd ..
+  $ rm -rf local
+  $ hg clone remote local -r 0
+  adding changesets
+  adding manifests
+  adding file changes
+  added 1 changesets with 1 changes to 1 files
+  updating to branch default
+  1 files updated, 0 files merged, 0 files removed, 0 files unresolved
+  $ cd local
+  $ mkcommit new
+  $ hg -R ../remote id --debug -r tip
+  c70b08862e0838ea6d7c59c85da2f1ed6c8d67da tip
+  $ hg  id --debug -r tip
+  71e3228bffe1886550777233d6c97bb5a6b2a650 tip
+  $ hg debugobsolete c70b08862e0838ea6d7c59c85da2f1ed6c8d67da 71e3228bffe1886550777233d6c97bb5a6b2a650
+  $ hg glog --hidden
+  @  71e3228bffe1 (draft) add new
+  |
+  o  b4952fcf48cf (public) add base
+  
+  $ hg glog --hidden -R ../remote
+  o  c70b08862e08 (draft) add old
+  |
+  @  b4952fcf48cf (public) add base
+  
+
+Push should not complain about new heads.
+
+It should not complain about "unsynced remote changes!" either but that's not
+handled yet.
+
+  $ hg push --traceback
+  pushing to $TESTTMP/remote
+  searching for changes
+  note: unsynced remote changes!
+  adding changesets
+  adding manifests
+  adding file changes
+  added 1 changesets with 1 changes to 1 files (+1 heads)