I know what a pain in the tukus that is.
Here's what I do.
(1) be sure the COS of the phone has the option to Erase Messaging waiting then at the phone hit the msg key, read messages, erase.
(2) At the phone hit from the main line, dial the message waiting on code and then the message waiting off code. Twice.
(3) Be sure that all your VM ports in in a single hunt group. Assumes you have embedded vm. Then add a phone with a VM COS, enter the msg waiting on code then the off code. If there are more than one VM hunt group, add the phone to each of them one at a time, then enter the on/off code.
(4) renumber the extension to something else. Rebuild the phone.
Ralph