That's callpilot 4.0. We support a CallPilot 4.0 (04.04.04) installation that uses Desktop Messaging & Lotus Notes. They've been running over 13 months on CP 4.0 and had no problems with deleting voicemail. (I'm the engineer assigned to keep them happy as they one of our customers that regularly spend a lot of money with us... so if they had problems, I would have heard about it.)
What version Desktop Messaging client are you using?
You should be able to get this information by double-clicking on a voicemail and selecting Help|About from the voicemail player.
The latest Desktop client version is 04.04.04.18. If you're not using that, upgrade that first. When the customer upgraded their Lotus Notes server without talking to us, they started running in to all sorts of problems with the Desktop Messaging client because they were using 04040412 (I think) which wasn't compatible with Lotus Notes 8 and client.