Have they changed their settings that it automatically pulls more than the first 1,000 records? I've found that people with large files need to ""perfect"" the individual searches before modifying this setting.
Also, I assume this is a network environment, have their Anti-Virus programs changed or been updated? I have seen these conflict, although rarely.