If it's happening to only one group (department) on the domain, I would suspect the network equipment/settings and not Office 2003. If it was Office, they would all have the same problem. There appears to be a conflict somewhere.
Try taking just one computer out of this group into a different room where you know the cabling goes through a different switch/hub/router, log into the domain from there and see if the problem persists. You may even try logging into a different department group with different user credentials. Try to narrow it down to being either location specific (one area in the building) or group policy specific (what happens if a user in a different department logs in at the new location or where it was sitting before at the original location).
Like I said, if all users are using the same software and only one group has problems, it's not the software that has the problem.