Say it with me: Excel is not a database.
You're running up against the design limitations of the software: it's only got so much ability to store transactional data, so when multiple people are writing to it, it has to store a frickton of information in order to reconcile. You have so much data in it, that the transactional copies are HUGE.
Microsoft assumes (correctly) that if you have that much data, it's stored in a database, and you're just using Excel as a front end.
If you're going to work like that, you should at least knock together a little Access database. It will save you a world of headache, because it's meant to WORK like that and Excel just isn't.
@Josh: Yes, it absolutely IS leaking. When you share a document, it has to keep track of the modifications done by every user...I'll call this "transactional data" but you can just think of it as history. Since there is never an "official" version, it keeps keeping track of changes, and the document bloats up faster than Kirstie Alley in a doughnut shop.
It's by design. Someone who is an excel guru may be able to tell you how to make it stop, but the best solution is just not to use excel for data that's being constantly maintained. It's not really what it's designed for.
I am sympathetic to your problem, but it's a better solution to explain the problem to the higher-ups and work out a new procedure, than it is to try and prolong an unfortunate hack.
@Josh: If you just want to shrink it once, temporarily, copy all the data, and paste it into a new spreadsheet. THAT will kill all the metadata, guaranteed (make sure you don't select the whole sheet, but only the part with data in it) But this is a temporary solution at best.
Best Answer
Most of the problems I've seen with shared Excel files have to do with the folder the spreadsheet is in because of temp files, so you can check to make sure all the users using the file have read/write/delete access to the folder (although I'd imagine this is already true because your users can use it normally with 1 change at a time now).
The other thing you can do to try and clean up any issues is reset the sharing. Have everyone close it out, and open it up yourself. In the sharing dialog, it will show you the users who have it open, and you should make sure it only shows yourself. Remove any other users listed as having it open. Then, choose to unshare the file, and save it. Clear out any temp files alongside the spreadsheet, and make sure you (and the other users) can open, save changes, and close the file normally one at a time. If that goes ok, have one person open it and make it shared again. That might clean up whatever issues you were having, but note that this will remove any change history if you keep it.
Another option that you might have is to upgrade Excel. I don't know how possible this is in your situation, but Office 2007 and Office 2010 will handle the large file more efficiently, and this might correct your problem if nothing else works.