Logging into exchange from another domain

We have two domains in two different locations. There is an Exchange Server 2003 at one site that some people in the other domain use. There’s no trust between the two, but the firewalls are configured to recognize both. The remote users are not required to change their passwords, however many times some of them are consistantly needed to have me reset their passwords (sometimes daily), before they are able to get their email. Even if the passwords are the same on both domains they are prompted for passwords. Anyone deal with this issue? One problem is that the remote people never have the need to actually log onto the domain that hosts the Exchange server, only get their mail.