So on the Cisco side you have checked all of the following ?
On the VPIM system:
Administer the Message Networking system as a VPIM network node on the VPIM system. You might need the following information, depending on your VPIM system type:
The fully qualified domain name and IP address of the Message Networking system. The VPIM system uses this information to send messages to the Message Networking system.
The Message Networking network address length.
The Message Networking network address ranges for other messaging systems in the network. Depending on the specific VPIM system, the address ranges that are required are generally the dial plan mapping entries for each remote machine on the Message Networking system. In other cases, you might need all digits of the address ranges. In addition to the dial plan map, you might need to add a prefix to address messages to the Message Networking system.
If you need to specify a server type, obtain this information from the VPIM system administrator.
If you need to specify a protocol type, select VPIM.
Note: The VPIM system must pass to Message Networking only those addressing digits used in the Message Networking network. When using telephones, subscribers on the VPIM system might have to dial additional digits to address messages to remote subscribers on the Message Networking network. This is sometimes referred to as a prefix. These digits might be required for the following reasons:
The VPIM system can identify the addressee as a remote subscriber.
The VPIM system can identify the remote system where the remote subscriber resides (in this case, the Message Networking system).
Do not administer the VPIM system to pass any other digits to the Message Networking system. Instead, administer the VPIM system so that it strips off these additional addressing digits when it passes the message to the Message Networking system. Only addresses within the ranges specified for Message Networking remote machines (specified in the Dial Plan Mapping) are to be sent to the Message Networking system.
Ken Means
"I find that the harder I work, the more luck I seem to have."
- Thomas Jefferson (1743-1826)