Hi,
Have you run through all of the scripts that need to be run on Exchange UM and OCS? For exchange it's the exchucutil.ps1 and for OCS it's the ocsumutil.exe. Assuming you have... then I would try:
1) taking a new user and UM-enabling them only on the OCS dialplan.
2) Enable that user for EV in OCS,
3) open MOC and verify that the VM option is there
If this works, just add the other dialplan EUM address to the user in Exchange.
Regards,
Matt