Can’t delete

We have Exchange 5.5 SP3 running on a Win 2k server which is a member of a NT4 Domain. Our Mail clients are all Outlook 2000 running on everything from 95/98 to 2k to me. If we try to delete more than one mail message at a time, or a folder (even an empty folder) Outlook stops responding. Any ideas?