After the decision to ignore undecodable file names in os.listdir but before PEP 383 there was a long discussion on python-dev (in which I was a participant) about how horrible just ignoring the undecodable filenames was.  This applies *especially* to the os.walk case, where some files would be mysteriously skipped and it wouldn't be obvious why.
Or even obvious that they'd been skipped, in some cases.  The biggest issue was that the developer would likely never see the problem since the bulk of developers don't encounter encoding issues, so it would be the poor end user who would be confronted with the mystery, with no clues as to the cause or solution.

The conclusion of that particular thread was that Guido approved adding warning messages for filenames that were undecodable, but otherwise leaving os.listdir unchanged.  Fortunately Martin came up with PEP 383, which solved the underlying problem in a better way.

So, I don't think that skipping the undecodable names is good, unless you generate a warning.  In that thread I started out advocating raising an error, but in this case as Martin points out that would be a backward compatibility issue.  Returning the munged filenames and having the error show up when the broken filename is used seems OK to me, even if imperfect.  When the user sees the problem, they report it to the developer as a bug, who hopefully changes his code to use strings.

Adding warning messages would probably be useless at best and annoying at worst on Windows.  Maybe we could add a pseudo deprecation warning (ie: aimed at developers, silent by default) that says "don't use listdir with bytes on windows"?