Have you upgraded Alfresco recently? I ask because we changed the way the Simple/Advanced search forms queries by default - so you now have to explicitly add asterix * to match non-exact terms - whereas older versions of Alfresco would add a suffix * for you, newer versions do not.
Also, the search is now sensitive to locale of the user - so certain words my split up (tokenize) differently depending on the locale. Users may see different results depending on the current language locale they have selected.
Thanks,
Kevin