You have to setup the Exchange routing correctly between the sites. Basically, if you do not have the two exchange servers setup in the Exchange Org correctly, you may not be getting updates from each side.
Sounds like you are are on Voicemail only.
Log into http://mail.exchangeserver/exchange
Login in as UnityMsgStrSvc
You should get the Administrator account or whatever. Open up the Address book, can you see the other Exchange users on Server B? If you can not, then Exchange is not sharing, which is the problem.