You didn't say what phone you're using.
For display phones, set the COS to enable "Voice mail message waiting erasure allowed" to yes.
(I'm not exactly sure if that's exactly what it says so just look through the options and you'll find it.)
Once the phone is allowed to delete the msg waiting in COS, hit the msg waiting button on the phone, then the read msgs button, then call back button, then erase.
Ralph