A Medusa query of everything in my gnome2 build dir took 14 seconds 256 milliseconds to return 172,717 files, but display took 1 hour and 1 minute. Medusa knows everything but the icon, so msearch-gui had lookup the mime-type (again) in VFS to display the icon. Medusa could be doing a lot more, such as returning the full set of posix data, but extending it to handle icons would be difficult.
My point, in regards to Nautilus, is that it spends a lot of time traversing the disk (or net) and making repeated calls to get the specifics of each file. The file system is not designed to return a set of data like a database query, but that feature is what a modern file browser needs. That is was WinFS is reported to do. Content management systems also offer this kind of feature. Users now have gigs of data, hundreds of thousands of files. Enterprises use more than simple file systems to organize this amount of data, and so should users.
Now I question why anyone needs to see more than a few dozen files of anything; it is more than you can take in. Most likely the user is only looking for a few files. Directories are a weak means of organizing/classifying data, and users cannot easily ask for the files they want to see. A proper metadata DB would server Nautilus all the information it requests in a single lookup. A metadata DB would provide users and applications with the query features to keep the file list concise and relevant.
Directories and masses of poorly organized files is the here and now. Nautilus might ease the situation by doing a incremental display of files if a milestone is not met. It could get the list of files, sort them by access time, then begin display, so the most recent files (and commonly used) are the first the user can access.