Mailbox access into trusting domain slow [Outlook, Windows 2003]

I have run out of ideas for this issue and am seeking any help:
I have 2 domains, both are Windows 2003. Domain A contains user accounts and e-mail boxes. Domain B contains user accounts only. Domain A mailboxes are set to allow the corresponding users in domain B to access the mailboxes on servers situated in Domain B. This has worked great for some time. All of a sudden a few weeks ago, Outlook started opening extremely slowly for users logging into domain B. The same user can log into Domain A and open outlook immediately. These users are all logging into terminal servers. I have logged into one of the terminal servers in domain b as the admin and can access a mailbox on domain B immediately. However when I try to access a mailbox on domain A, outlook takes up to 5 minutes to load.
The only errors I see are on the terminal server in domain B:
1. source: .net runtime, Event id 0: unable to open shim database version registry key v2.0.50727.00000
2. Souce: microsoft office 11, event id 2000: accepted safe mode action: MS Outlook
3. Source: application hange, event id: 1002, hanging application outlook.exe version 11.0.80000.0, hang module hungapp, version 0.0.0.0, hang address 0x00000000.
At first this issue showed up on 2 terminal servers a day or two after upgrading to sp2. Rolling back the sp did not correct the issue. Other terminal servers have been running sp2 for sometime with no problems. Now we are getting intermittent reports of users on other terminal servers with a similar issue. I'm thinking it's some kind of issue between the domains but I don't know where to go next. Any assistance would be greatly appreciated.