I don't know if this is really a "solution" per se, but it's a workaround that I prefer anyway: I changed the "Arrange by" to "None" as described here Mac OS X - File Open Dialog: Can't sort or resize columns
This gets rid of the categorization by Today/7 days/30 days/etc. altogether, and just gives a straightforward dialog that lets you sort however you want (be it Date Modified, or Name, or Size). I find this much more useful and fail to see the advantage of the other view (which is made almost useless by this No Date bug).
Note that some applications (e.g., MS Office) do not let you change the Auto-arrange setting. Just open up some other application that does (e.g., Chrome) and set it there (just go to Open File or similar -- you don't have to actually open the file). This action seems to set this setting globally (on 10.8.4).
This problem is all over the web. Why does Apple not comment on it? Does it not care about its users? Why does it not release a fix? Is iTunes so much more important? This bug seems almost ludicrous: The arrange-by setting used for categorization is (normally) "Date Modified", and the actual modified date is clearly shown in the Date Modified column. Indexing in the general case perhaps needs to happen not in real time (e.g., if you are viewing "All Files"), but when we open a dialog, can't just the (usually very few but most important) No Date files be manually indexed in that moment?