diff --git a/mercurial/localrepo.py b/mercurial/localrepo.py
--- a/mercurial/localrepo.py
+++ b/mercurial/localrepo.py
@@ -1398,7 +1398,7 @@ class localrepository(object):
             self._phasecache.write()
 
     @unfilteredmethod
-    def destroyed(self, newheadnodes=None):
+    def destroyed(self):
         '''Inform the repository that nodes have been destroyed.
         Intended for use by strip and rollback, so there's a common
         place for anything that has to be done after destroying history.
@@ -1421,16 +1421,9 @@ class localrepository(object):
             self._phasecache.filterunknown(self)
             self._phasecache.write()
 
-        # If we have info, newheadnodes, on how to update the branch cache, do
-        # it, Otherwise, since nodes were destroyed, the cache is stale and this
-        # will be caught the next time it is read.
-        if newheadnodes:
-            cl = self.changelog
-            revgen = (cl.rev(node) for node in newheadnodes
-                      if cl.hasnode(node))
-            cache = self._branchcaches[None]
-            cache.update(self, revgen)
-            cache.write(self)
+        # update branchcache information likely invalidated by the strip.
+        # We rely on branchcache collaboration for this call to be fast
+        branchmap.updatecache(self)
 
         # Ensure the persistent tag cache is updated.  Doing it now
         # means that the tag cache only has to worry about destroyed
diff --git a/mercurial/repair.py b/mercurial/repair.py
--- a/mercurial/repair.py
+++ b/mercurial/repair.py
@@ -66,17 +66,6 @@ def strip(ui, repo, nodelist, backup="al
     striplist = [cl.rev(node) for node in nodelist]
     striprev = min(striplist)
 
-    # Generate set of branches who will have nodes stripped.
-    striprevs = repo.revs("%ld::", striplist)
-    stripbranches = set([repo[rev].branch() for rev in striprevs])
-
-    # Set of potential new heads resulting from the strip.  The parents of any
-    # node removed could be a new head because the node to be removed could have
-    # been the only child of the parent.
-    newheadrevs = repo.revs("parents(%ld::) - %ld::", striprevs, striprevs)
-    newheadnodes = set([cl.node(rev) for rev in newheadrevs])
-    newheadbranches = set([repo[rev].branch() for rev in newheadrevs])
-
     keeppartialbundle = backup == 'strip'
 
     # Some revisions with rev > striprev may not be descendants of striprev.
@@ -191,10 +180,4 @@ def strip(ui, repo, nodelist, backup="al
                     % chgrpfile)
         raise
 
-    if len(stripbranches) == 1 and len(newheadbranches) == 1 \
-            and stripbranches == newheadbranches:
-        repo.destroyed(newheadnodes)
-    else:
-        # Multiple branches involved in strip. Will allow branchcache to become
-        # invalid and later on rebuilt from scratch
-        repo.destroyed()
+    repo.destroyed()
diff --git a/tests/test-acl.t b/tests/test-acl.t
--- a/tests/test-acl.t
+++ b/tests/test-acl.t
@@ -1527,7 +1527,6 @@ Branch acl deny test
   query 1; heads
   searching for changes
   all remote heads known locally
-  invalid branchheads cache (served): tip differs
   listing keys for "bookmarks"
   4 changesets found
   list of changesets:
@@ -1839,7 +1838,6 @@ push foobar into the remote
   query 1; heads
   searching for changes
   all remote heads known locally
-  invalid branchheads cache (served): tip differs
   listing keys for "bookmarks"
   4 changesets found
   list of changesets:
@@ -1927,7 +1925,6 @@ Branch acl conflicting deny
   query 1; heads
   searching for changes
   all remote heads known locally
-  invalid branchheads cache (served): tip differs
   listing keys for "bookmarks"
   4 changesets found
   list of changesets:
@@ -2083,7 +2080,6 @@ Non-astro users must be denied
   query 1; heads
   searching for changes
   all remote heads known locally
-  invalid branchheads cache (served): tip differs
   listing keys for "bookmarks"
   4 changesets found
   list of changesets:
diff --git a/tests/test-keyword.t b/tests/test-keyword.t
--- a/tests/test-keyword.t
+++ b/tests/test-keyword.t
@@ -507,6 +507,7 @@ amend
   $ hg -q commit -d '14 1' -m 'prepare amend'
 
   $ hg --debug commit --amend -d '15 1' -m 'amend without changes' | grep keywords
+  invalid branchheads cache (served): tip differs
   overwriting a expanding keywords
   $ hg -q id
   67d8c481a6be
diff --git a/tests/test-mq-symlinks.t b/tests/test-mq-symlinks.t
--- a/tests/test-mq-symlinks.t
+++ b/tests/test-mq-symlinks.t
@@ -45,7 +45,6 @@ test updating a symlink
   popping updatelink
   now at: symlink.patch
   $ hg qpush --debug
-  invalid branchheads cache (served): tip differs
   applying updatelink
   patching file a
   a
diff --git a/tests/test-rebase-collapse.t b/tests/test-rebase-collapse.t
--- a/tests/test-rebase-collapse.t
+++ b/tests/test-rebase-collapse.t
@@ -263,9 +263,10 @@ Rebase and collapse - E onto H:
 
 
 Test that branchheads cache is updated correctly when doing a strip in which
-the parent of the ancestor node to be stripped does not become a head and
-also, the parent of a node that is a child of the node stripped becomes a head
-(node 3).
+the parent of the ancestor node to be stripped does not become a head and also,
+the parent of a node that is a child of the node stripped becomes a head (node
+3). The code is now much simpler and we could just test a simpler scenario
+We keep it the test this way in case new complexity is injected.
 
   $ hg clone -q -u . b b2
   $ cd b2
@@ -282,7 +283,7 @@ also, the parent of a node that is a chi
   $ hg strip 4
   saved backup bundle to $TESTTMP/b2/.hg/strip-backup/8a5212ebc852-backup.hg (glob)
 
-  $ cat $TESTTMP/b2/.hg/cache/branchheads
+  $ cat $TESTTMP/b2/.hg/cache/branchheads-served
   c65502d4178782309ce0574c5ae6ee9485a9bafa 4
   2870ad076e541e714f3c2bc32826b5c6a6e5b040 default
   c65502d4178782309ce0574c5ae6ee9485a9bafa default