One factor that may be an issue is this:
even if you have the locations in question selected for Indexing, a change of permissions can throw a wrench in the works. For example, if you've changed permissions on a folder so that only you (user x) can access or change the files (meaning that no other permissions are listed), it will not index. You must add 'System' back to permissions so that the folder may be indexed.
There is no notification that search will 'break' under these circumstances, but firsthand experience verifies it here. This may not be your problem, but worth checking.