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 'The existing Spotlight index will be erased and a new Spotlight search index rebuilt in the background. Your system may run slower whilst this is happening and could take many hours'.
