There seems to be a lack of information out there, even with some TAC engineers, about how to prepare Cisco Unity to import subscribers from Exchange servers in AD domains different from the one in which Unity is installed. I've even had several Cisco engineers tell me that this is unsupported, which is totally false. As far as I know, these are the requirements for Unity with respect to multiple domains:
1) All Exchange servers from which you want to import subscribers must be in the same AD forest. Unity unified messaging does not work across multiple forests. Of course, you can still create voicemail boxes that are totally independent of AD, but that's not the point of unified messaging. Exchange servers in different domains in the same forest is not a problem, as long as the PES (see below) is in the same domain as Unity.
2) The Unity server(s) must be installed in the same Active Directory domain as the partner Exchange server, or PES. You specify the PES during the Unity install process. It can be changed with the Message Store Integration Wizard. The PES must have Exchange routing group connectors to all other Exchange servers from which you want to import subscribers. More info on changing the PES is here.
3) You must run the Permissions Wizard on the Unity server while logged in as an account that can set permissions in all the domains containing Exchange servers from which you want to import subscribers. This might require running the PW multiple times under different accounts. This works fine. You may need to add a domain admin account from another domain to the local admin group on the Unity server. When you run PW from accounts in different domains, it will probably fail on some of the domains. This is because you probably won't have a single account that has all the required permissions in all the domains. You just need to continue running PW under different accounts until it has succeeded in all the domains that have Exchange servers from which you're importing subscribers.