MySite and MyProfile links missing in SharePoint 2010 for some users

Two things. First, make sure that the content database is set to online (Central Admin -> Web applications -> Content Databases) and not offline. When offline user name changes do not propagate.

Since you said this is MOSS, make sure your SSP user profiles are set to synchronize on a schedule (they are not by default). Set a schedule if not set up.

You can also try to force a user profile synchronization them by running stsadm -o sync

I'm also think that domain trusts is good idea for your task. I have successful experience with it: In my case Each domain had its own intranet-portal based on MOSS 2007. It was necessary to provide access to both portals for users from both domains. We created up a two-way trust relationship between forests and grant all necessary permissions. My env is standard: AD, 2003, MOSS 2007.

In my opinion, there are two another methods. Probably they will be better for you:

1. If both of your domains are in one secure LAN networks, you can allow anonymous access to your portal.
2. You can create accounts in your domain for users from external domain. In that case users from external domain will need to use form-based authentication (not windows auth)

You can mix those two methods. Lets say that you can grant anonymous read access for all and create few accounts in your domain for users, who need contributor rights on intranet-portal.