Unity Version 7.0(2.0). Tried deleting user then imported user back into Unity. This did not resolve the problem.
This sounds to me like you are in UMR (Unity Message Repository) Mode where Unity can't see the Exchange server so it stores all voicemails locally on the server. This would explain why the messages never show up in Outlook but are there when you login to your phone and you can listen to them but not delete them. Listen to the message when you login to check voicemails. It should tell you your message store is offline but you can still check messages. If so, you need to find out why Unity can't see Exchange. Here is the troubleshooting guide that addresses this issue.