Not sure quite what your customer is hoping for - Unity has the option of keeping deleting items in the deleted items folder - which allows you to retrieve them. With this option disabled when you delete a message, it's gone - Unity does not have a seperate copy of voice mails somewhere external to Exchange it can draw on for this - Exchange (or Domino) _is_ the mailstore in this case. If they've opted to delete messages without saving a copy in the deleted items folder, it's gone.
There's a _very_ outside chance the Exchange mailstore may have a copy of the message in its dumpster, but normally this is cleared out in 24 hours (Exchange controls this, not Unity). You can checkout Microsoft's ExMerge to instructions on how to pull messages out of Exchange's dumpster if you want to pursue this.
