Can’t add Mailbox in Outlook – Exchange

Using Exchange 5.5 and Outlook 98 and 2000.

We have users that need to access several Exchange Mailboxes at the same time. In Outlook you go to Tools / Services / Exchange / Properties / Advanced, and add the Mailbox. For an increasing number of users, we can’t add a Mailbox. Just clicking the “add” button gives this error: “The name could not be resolved. The action could not be completed.” How do we solve this? This happens on OL98 and OL2k clients.