Thanks all for your suggestions.
ET - Yes, I had a look at your advice and allowed all the joining and external transfer under features for all voicemail terminals, and amazingly its started working! Yes, its was a feature issue but more on the voicemail side rather then the users/hunt group end. Thanks for your help on this.

Also, not sure if you guys read the second issue or not. We also need to use free dialing to allow external calls to dial extensions on the remote switch. Free dialing local station works fine, however when we try free dialing the remote extension (anything in 300 range) the AA prompts this as an invalid entry?
Can remote extensions be dialed using free dialing or am I chasing shadows? :-p
Cheers!