LOL what a shame... :)
I ran into the same river again after I accidentally set new GPO User policy (Admin Templates\Start Menu\Remove Network Connections from Start Menu) and applied such policy to a computer account instead of a user account.
After googling for help I found my own solution hahaha :) nice thing :)
Now I'd like to explain the thing in details since it seems to be a bug for me. Since User policy settings are not being processed when applied to computer account, above policy should have no effect.
Well. IT DOES. It looks that Windows 2000 applies such policy computer-wide (all domain accounts inlcuding admins) and the funny thing is that you won't see that in gpresult (no such was policy processed neither under Computer nor under User tab).
And now final solution: It won't help if you create "anti-policy" (user settings) and apply it to affected computer account (this it won't be processed by design). In order to get rid of this crap you need to DISABLE this setting in Domain Computers policy, run gpupdate /force on server and reboot affected w2k workstation. Then sinc issues is fixed you can reset Remove Network Connection in Domain Policy to whatever state it was before.