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
The problem was the Office File Validation, which was pushed via Windows Update this week. I was able to introduce this problem on a separate network. Removing Office File Validation solves the problem.
This patch was only for Office 2003 and 2007, so 2010 is not affected.
http://support.microsoft.com/kb/2501584
MS KB update: http://support.microsoft.com/kb/2570623