Just some thoughts. This is more of a troubleshooting issue than a simple question/answer. Things to look into:
1. Are they sharing Excel files and is it happening when they do that?
2. Are the hard drives cleaned up? See:
http://www.thewordexpert.com/cleanyourpc.htm
3. Any possibility the docs are corrupt? I assume you've checked that out.
4. Do these user's have the autosave addin turned on by chance? Not a good thing--it doesn't work like Word's. Pardon my french, but it sux andcauses problems. Are they running any addins?
5. Have you dumped the registry key in Excel on these PCs? Let me know if you don't know how and want to give it a shot.
6. Anything in their XLSTART folders? Is the XLSTART on a network drive (nota good thing-just adds network issues to running Excel).
7. Anything under their Alternate startups? Tools-Options, General tab, Alternate startup folder.
I'll assume you've done any upgrades, you don't mention the version of Office...
Hopethey help!!
~Dreamboat