Trusted Domain Mailbox Permissions

[mayh3m]

Hi Everyone

We are running active directory with Win 2003 and exchange 2003. Recently, we created a trust between another 2003 domain and ourselves and found that the users in that domain could no longer log onto their mailboxes. (We host the domain that our mail runs on)(Reason was Logon Failure)
We could only solve this problem by giving their user accounts on their domain account permissions to the mailbox on our side and adding the "Assosciate external account" permission to "Self". We did this manually for 900 users. We are now creating another trust for a seperate domain and have tested in the lab and found that the same thing happens. Is there no was around this? Or maybe a script that automatically links the user accounts on the trusted domain to the mailbox instance on our side. This will effect in the region of 3000 users, so manually linking these users is a scary option.
Your assistance is appreciated.

Please let me know if I can clarify this question in any way.

 

[mayh3m]

Anyone seen this? I'm rather desperate, and I'm sure someone must have had this before. It will happen in any setup.
I'm sure the reason is this - previously, the users used to log onto their domain (not related to us) and then open outlook which notices they were on a seperate domain. It would then prompt them for a logon where they would put "ourdomain\username" and "password"
Whats obviously happening now, is that they log onto their domain which is trusted by ours. When they open outlook it tries to authenticate and sees that their domain is trusted by ours, but that the user account does not have permissions to the mailbox. This I suppose you can relate to someone logging on to our domain that does not have permission to mailbox "A" and tries to open mailbox "A"
Please help!