diff --git a/lib/bb/cache.py b/lib/bb/cache.py
index 24bde62a9..d05d341f4 100644
--- a/lib/bb/cache.py
+++ b/lib/bb/cache.py
@@ -619,7 +619,8 @@ class Cache(object):
                     if not f:
                         continue
                     f, exist = f.rsplit(":", 1)
-                    if (exist == "True" and not os.path.exists(f)) or (exist == "False" and os.path.exists(f)):
+                    file_exists = bb.parse.cached_mtime_noerror(f) != 0
+                    if (exist == "True" and not file_exists) or (exist == "False" and file_exists):
                         self.logger.debug2("%s's file checksum list file %s changed",
                                              fn, f)
                         self.remove(fn)
diff --git a/lib/bb/parse/__init__.py b/lib/bb/parse/__init__.py
index d428d8a4b..815ff1279 100644
--- a/lib/bb/parse/__init__.py
+++ b/lib/bb/parse/__init__.py
@@ -48,18 +48,22 @@ class SkipPackage(SkipRecipe):
 
 __mtime_cache = {}
 def cached_mtime(f):
-    if f not in __mtime_cache:
+    # A cached 0 is a failure recorded by cached_mtime_noerror(), stat again
+    # to raise the real error (or pick up the file if it has appeared since)
+    if __mtime_cache.get(f, 0) == 0:
         res = os.stat(f)
         __mtime_cache[f] = (res.st_mtime_ns, res.st_size, res.st_ino)
     return __mtime_cache[f]
 
 def cached_mtime_noerror(f):
+    # Failures are cached as 0 so that repeated lookups of a missing file
+    # don't hit the filesystem again
     if f not in __mtime_cache:
         try:
             res = os.stat(f)
             __mtime_cache[f] = (res.st_mtime_ns, res.st_size, res.st_ino)
         except OSError:
-            return 0
+            __mtime_cache[f] = 0
     return __mtime_cache[f]
 
 def check_mtime(f, mtime):