Has it always been checked? I do not believe it is by default. If you did check it recently were the services restarted? Changing the check box is not retroactive.
You could delete the contents of the PSTComputer table in the directory database and repopulate the list.
However I *
would not* recommend doing this if you have already started to migrate PST files from computers. Of course if the are all set to do not search I doubt it. :)