diff --git a/mercurial/store.py b/mercurial/store.py
--- a/mercurial/store.py
+++ b/mercurial/store.py
@@ -5,6 +5,7 @@
 # This software may be used and distributed according to the terms
 # of the GNU General Public License, incorporated herein by reference.
 
+from i18n import _
 import os, stat, osutil, util
 
 def _buildencodefun():
@@ -77,14 +78,14 @@ class _store:
             if (len(f) > 2) and f[-2:] in filetypes:
                 yield util.pconvert(f[striplen:]), size
 
-    def _datafiles(self):
+    def datafiles(self, reporterror=None):
         for x in self._revlogfiles('data', True):
             yield x
 
     def walk(self):
         '''yields (direncoded filename, size)'''
         # yield data files first
-        for x in self._datafiles():
+        for x in self.datafiles():
             yield x
         # yield manifest before changelog
         meta = util.sort(self._revlogfiles())
@@ -95,7 +96,6 @@ class _store:
 class directstore(_store):
     def __init__(self, path):
         _store.__init__(self, path)
-        self.encodefn = lambda x: x
         self.opener = util.opener(self.path)
         self.opener.createmode = self.createmode
 
@@ -107,9 +107,14 @@ class encodedstore(_store):
         op.createmode = self.createmode
         self.opener = lambda f, *args, **kw: op(self.encodefn(f), *args, **kw)
 
-    def _datafiles(self):
+    def datafiles(self, reporterror=None):
         for f, size in self._revlogfiles('data', True):
-            yield decodefilename(f), size
+            try:
+                yield decodefilename(f), size
+            except KeyError:
+                if not reporterror:
+                    raise
+                reporterror(_("cannot decode filename '%s'") % f)
 
     def join(self, f):
         return os.path.join(self.path, self.encodefn(f))
diff --git a/mercurial/verify.py b/mercurial/verify.py
--- a/mercurial/verify.py
+++ b/mercurial/verify.py
@@ -158,9 +158,22 @@ def _verify(repo):
                 err(lr, _("in manifest but not in changeset"), f)
 
     ui.status(_("checking files\n"))
+
+    storefiles = {} 
+    for f, size in repo.store.datafiles(lambda m: err(None, m)):
+        if size > 0:
+            storefiles[f] = True
+
     files = util.sort(util.unique(filenodes.keys() + filelinkrevs.keys()))
     for f in files:
         fl = repo.file(f)
+
+        for ff in fl.files():    
+            try:
+                del storefiles[ff]
+            except KeyError:
+                err(0, _("missing revlog!"), ff)
+
         checklog(fl, f)
         seen = {}
         for i in fl:
@@ -205,6 +218,9 @@ def _verify(repo):
             for lr, node in util.sort(fns):
                 err(lr, _("%s in manifests not found") % short(node), f)
 
+    for f in storefiles:
+        warn(_("warning: orphan revlog '%s'") % f)
+
     ui.status(_("%d files, %d changesets, %d total revisions\n") %
                    (len(files), len(cl), revisions))
     if warnings[0]: