This vexes me greatly. I have read of the mdutil command, but my understanding is it must be entered each time you log on, which just isn't going to work in a multi-user environment. Furthermore, if the NAS is huge, it seems to really slow down computers that are indexing.
Is there no surefire, automated solution for network users to search a NAS?
Slow searching generally means walking the filesystem looking at each file. This is easily done over any remote filesystem protocol (SMB, AFP, NFS). Whether or not your client box's OS has an easy way to do this is a different question. Mac users who aren't very Unix savvy probably don't want to run the command-line "find" command. And generally, this kind of "walk the filesystem" searching is only appropriate for searching by filename or other metadata, not contents.
Fast searching usually requires that a process on the file server (the NAS box in this case) creates and maintains a separate database/index of file metadata (and possibly file contents keywords), so that fast searches can be executed against that database. The tricky parts of this are (1) that different fast searching solutions for different OSes have different ideas of what this index should look like, and (2) you need to make sure this database/index doesn't leak information about files that the user doing the search doesn't have access to.
So you're right, there still is no cross-platform standard for fast searching of NAS filesystems.
If you're mostly supporting Mac users, consider creating a pseudo-NAS by buying a Mac mini (US$499) running OS X Server (US$20), and hook it up to a Thunderbolt drive or Thunderbolt desktop RAID (US$250 + drives). OS X Server has facilities for maintaining a Spotlight index on the server so that your Mac clients can just use it when they connect.
For Mac users I recommend Foxtrot. It's a commercial product. Once you buy enough client licenses it comes with a server indexer for free. The server indexer can run on either Mac or Windows (although setting up correct path translation for Windows can be frustrating) I have ours running on an Xserve, which has mounted an EMC Isilon via NFS (which could also be Local, AFP or SMB) The indexer has its own scheduler, where it can run periodically, user management, no integration with directory services.
The client is run on each Mac (there is no windows version) the user logs in and then performs a keyword search, if the translation paths are set correctly it will also show a preview of the document, using the standard Mac Previewer/quicklook by pointing to the file on the shared drive.
