diff --git a/mercurial/tags.py b/mercurial/tags.py
--- a/mercurial/tags.py
+++ b/mercurial/tags.py
@@ -494,11 +494,25 @@
     starttime = util.timer()
     fnodescache = hgtagsfnodescache(repo.unfiltered())
     cachefnode = {}
+    validated_fnodes = set()
+    unknown_entries = set()
     for node in nodes:
         fnode = fnodescache.getfnode(node)
+        flog = repo.file(b'.hgtags')
         if fnode != nullid:
+            if fnode not in validated_fnodes:
+                if flog.hasnode(fnode):
+                    validated_fnodes.add(fnode)
+                else:
+                    unknown_entries.add(node)
             cachefnode[node] = fnode
 
+    if unknown_entries:
+        fixed_nodemap = fnodescache.refresh_invalid_nodes(unknown_entries)
+        for node, fnode in pycompat.iteritems(fixed_nodemap):
+            if fnode != nullid:
+                cachefnode[node] = fnode
+
     fnodescache.write()
 
     duration = util.timer() - starttime
@@ -826,6 +840,21 @@
 
         self._writeentry(ctx.rev() * _fnodesrecsize, node[0:4], fnode)
 
+    def refresh_invalid_nodes(self, nodes):
+        """recomputes file nodes for a given set of nodes which has unknown
+        filenodes for them in the cache
+        Also updates the in-memory cache with the correct filenode.
+        Caller needs to take care about calling `.write()` so that updates are
+        persisted.
+        Returns a map {node: recomputed fnode}
+        """
+        fixed_nodemap = {}
+        for node in nodes:
+            fnode = self._computefnode(node)
+            fixed_nodemap[node] = fnode
+            self.setfnode(node, fnode)
+        return fixed_nodemap
+
     def _writeentry(self, offset, prefix, fnode):
         # Slices on array instances only accept other array.
         entry = bytearray(prefix + fnode)
diff --git a/tests/test-tags.t b/tests/test-tags.t
--- a/tests/test-tags.t
+++ b/tests/test-tags.t
@@ -452,8 +452,8 @@
   5 8dbfe60eff306a54259cfe007db9e330e7ecf866 0c04f2a8deadde17fab7422878ee5a2dadbc943d (unknown node)
 
   $ hg tags
-  abort: data/.hgtags.i@0c04f2a8deadde17fab7422878ee5a2dadbc943d: no match found
-  [50]
+  tip                                5:8dbfe60eff30
+  bar                                1:78391a272241
 
 BUG: Unless this file is restored, the `hg tags` in the next unix-permissions
 conditional will fail: "abort: data/.hgtags.i@0c04f2a8dead: no match found"