We work with Prostar 816s all the time. Ran into this problem not long ago actually.
If the cancelling doesn't work, just hit the msg key and it should ring the last phone that left you the msg. When someone picks up on the phone that left you the message, it will clear that message. Do that until all the messages are cleared. Note: the phone where the message came from must be answered when your msg key dials to it.