Yes, you can create 2 way forest trusts in windows 2003. They are called cross forest trusts or 2-way transitive forest trusts. Very cool, you create 1 trust at the top level and you can access any child domains from either site (Transitive). If you have very large forests on each side this can create bottlenecks. You may need some shortcut trusts if this is the case.
Windows 2003 R2 definitely adds alot more to the forest side of things:
I have been looking into this type of an issue for a 3500 user network migration from Novell Groupwise to MS Exchange 2003 across the world. This also includes some sites setup as separate forests. Unfortunately forest trusts are out of the question for us so we will be using some sort of product to replicate information. Forest trusts might solve this issue of GAL replication though for me this is untested. DNS would probably need to be good between the forests for lookups (Conditional forwarders etc).
NickFerrar is correct; MIIS does allow this replication between separate forests to occur. For me, this is quite a new product from Microsoft so on this scale there is alot riding on it. Another alternative (what we will be using) are some of the Quest range of products. They are proven and have been around for a while.
(I forget the exact product; I will let you know when I remember its exact name)
My guess on the Exchange side of things, you will need local installs relative to each forests. The above tools replicate the GAL side of things. Mail replication may be a huge issue for you not to mention what the clients do. I am assuming that you have alot of clients (you haven't mention how big your network is) this may be a huge issue.
Hope this helps, goodluck
"Assumption is the mother of all f#%kups!