VBA can be pretty horrible to use - but it would be the shortest distance from what you've got to (something like) what you want. If you want a good solution that will work well and last a long time, I'd say go with the option of using a database. That way everyone can share a central data repository instead of passing around independently edited documents and trying to merge changes, which is notoriously difficult to do well at the best of times. Although this does fall foul of your requirement not to add any additional software, the software you add could easily all be free (I'm thinking Apache and MySQL; these will run on your Win32 boxes very happily and you wouldn't need any more than a spare desktop PC to run the server really). You could even just use MSDE - I suspect I'm right in thinking to 2Gb database size restriction wouldn't cause a problem any time soon
The advantages of moving to a central database are incalculable. It is a bit more work, but maintenance of busy Excel spreadsheets is like water torture so it would pay off in the long run.