Now you have me curious [:)] Can you give some specific worms that were successful? Who's your antivirus vendor and how frequently do the lappies get updates? The machines have strong local-admin passwords and are kept patched up, right?
You might try Microsoft Baseline Security Analyzer on your laptops too. The original WinXP-created Administrator account is not normally visible, but still can be exploited. MBSA will tell you if its password is weak or blank (duh). Changing the original Administrator account's name and giving it a hellaciously-strong password might help you prevent infections via the Admin shares.
At the risk of telling you something you already can do in your sleep, right-click My Computer > Manage > Users & Groups > Users, find Administrator, right-click, rename, right-click, set password. If you're logged on as a Domain Admin, you can do this to any computer that's on your LAN (again, sorry if I'm telling you 50 things you already know).
MBSA, maybe you use this already:
http://www.microsoft.com/downloads/details.aspx?FamilyID=b13ebd6b-e258-4625-b0a3-64a4879f7798&displaylang=en
Having read lots of worm descriptions, I also would use scanning within compressed files (real-time and scheduled scans) and maxed-out heuristics. In McAfee's case, this helps increase detection of unidentified worms.
EDIT: If the machines are all Win2000 then I guess my thing about the hidden Admin account doesn't apply, ooops! [:$]