Completely reset and rebuilt the Spotlight index for all users. There are various command line tutorials for doing this online when it starts to go 'screwy'.
However, this is difficult for non-technical users to do.
There should be a warning before the action is performed informing users that...