Hi -
I believe the Cisco Unity voicemail licensing covers the Exchange CAL, whether it is installed on same server as Unity or on a separate server. You'll want to read the information about separating Unity/Exchange in the reconfiguration guide -http://www.cisco.com/en/US/products/sw/voicesw/ps2237/products_upgrade_guides_chapter09186a0080205a84.html
I could not find a specific statement in the Unity licensing FAQs or document that covered the Exchange CAL info, but I did find this mentioned in the 4.2(1) mixed licensing document, that says "When using a mixed license, we recommend that you track the number of UM licenses and VM licenses against the total number of licenses you purchased. One way to do this is to segment the subscribers into different classes of service, and to place the user accounts into different OUs. Another consideration when licensing a mixed UM and VM solution is that all subscribers will reside in the same messaging infrastructure. This means that if your Unified Messaging subscribers are already licensed to use Microsoft Exchange, additional Exchange licenses (CALs) to support the mixed UM/VM solution are not necessary. The Voice Messaging users will now have Voice Messaging Exchange mailboxes and the licenses for these mailboxes are covered under the Cisco Unity software license." That document is - http://www.cisco.com/en/US/customer/products/sw/voicesw/ps2237/products_white_paper09186a0080623fa8.shtml#wp37939
Ginger