Policies

I don't have win2000 boxes but I use policies on my NT domain with NT workstations. I suppose that in win2000 boxes must be the same.
About if the policies are loaded or not
On all workstations I have on taskbar an icon which show me if a computerloaded the policies. Also you can test with some inoffensive settings like, restrict access to display properties for one user.
-if in your network exist a BDC or more, you must copy these policies in NETLOGON share of BDC. Also be sure that this was saved in the same share on PDC.
-default computer in policies (use policies editor) must have enabled and use default path (or enter other path if you don't save Ntconfig.pol in NETLOGON share) if you want applied this policies toall computers.
About outlook settings
Here I think that the problems are the users profile. I assume that you are using roaming profiles. Default path for user folder is on C local drive. If computer is used by more than one users exist the possibility to point at the same location. Personal I defined a share on server with subfolders for each user and I set the permission to allow access only for that user. The outlook settings are saved in save process of the profile. If the roaming profile don't work properly then you will lose these settings. If the workstation prompt the users to chose local or roaming profiles they must chose roaming profiles in order to keep their settings.
Please post comments for detail or other issues.

While I am no novice but yet not an expert, I would suggest checking the user profiles. All NT systems and 2000 I believe read .man and .usr profiles.
If your users are in groups use a mandatory profile with use of .man extension on the profiles, this way all users except those who are required to have a individual profile will have the same profile.
Then check the registry with a registry checker, it may be possible that there are some conflicts in the registries of the machines.

The I would have to ask, what service pack you have applied currently. And wether the problem existed prior to having win 2000 pro clients. before I could answer further.