I don’t know if this is what’s causing the problem for you, but I’ve seen several cases where this was caused by anti-virus software. The anti-virus software locks the temp file that Excel creates as the first step
in saving a workbook while it scans it. The temp file doesn’t get unlocked quickly enough so Excel throws a sharing violation error. Try disabling all your dynamic anti-virus scanning and see if the problem goes away.
You say that you do not have the issue on machines with Outlook 2007 – are the machines set up the same way with the same antivirus?
Do you have any spyware scanners running or other active scanning programs?