we just migrated from Exchange 5.5 to 2003 last year and it worked fine on same network but we had them as part of the same domain, not separate. the problem we had was trying to migrate the public folders over to the new server. make sure before you start to migrate them to export them to a PST file first. the pfmigrate steps that microsoft has to move them over take forever and there is no progress indicator to let you know how far they are. After 10 days ours still was not finished so we had to scrap it a rebuild them. When you start the pfmigrate it makes the folders on both systems inaccessible to everyone including system admins until all folders are done. it is a pain in the butt.

You are adding another level of difficulty by having them in separate domains. If the domains are part of the same forest I don't see why they would not be able to migrate between each other as long as each domain trusts the other. But I have not tried this so I am not sure. Anyone else out there have this situation before.