I have a client running Presence 7, Unity 7 and Exchange 2007. Have a problem when they delete a voicemail from the CUPC client. It doesn't delete it on Outlook.
I've been able to duplicate this at my office. CUPC seems to have some kind of control over messages within the mail store because I can mark my voicemails as "read" or "unread" and they change within Outlook. Deleting is another story though.
After deleting a message, the CUPC client has another option to "Purge" but this doesn't delete the messages either.
Last but not least, last week my office was on Exchange 2003 and it worked perfectly. I'm guessing it could be a permissions issue within 2007...just don't know where to look.