Exchange 2000 Problem

Hello all.
I have a problem connecting with Outlook 2000 to Exchange 2000 server on a Win2K domain controller.
Here is the full story:
Some time ago, one of the admins installed some security lockdown features on the server (i guess after nimda worm). Since than everybody is complaining that they can't see the global address list in Outlook. They can still send and recieve mail though.
So I removed exchange connector from on of the working machines here, and tried adding it back, but here is the problem: when i click on check name i get a message that the name "couldn't be matched to the name in the address list". But it does. I can view the list from the server, and the name is there. By the way, the same is happening with any name, even administrator.
So i've checked permissions on the address lists. "Everyone" plust each individual user has full control over them. I've check domain security policy, local police and DC security police, but couldn't find anything.

Any comments are greatly appreciated,
Victor