I've run into a recurring problem in which Spotlight stops working--entirely or in part--for my network user accounts.
Often, I'll notice that the Mail.app search feature no longer works. Interestingly, the most recent failure was that the "entire message" option would produce no results while "subject", "to", and "from" would search my mail successfully.
This has occured on other user accounts hosted by the same machine. Some users have found that their entire spotlight system (menu bar search, etc) fails to function.
Last time I just went into the server and chown/chgrp all the user accounts. For some reason, this forced spotlight to re-index and the spotlight issues went away for about a month. Now they are beginning to return.