Sounds dumb, but try unplugging/count 10/plugging in the phone. If that doesn't work try deleting and adding back the VMMSG button.

After that you might try deleting and adding back the mailbox in Cadence (try it on an unused extension/box first, if you have one).

Is this the iDCS 500 with 4-digit extension numbers? Or did you reset that to 3 digits? If the former then that may be the issue, I've never tried to use differing switch/VM extension/box numbering plans in the same system (nor have I run a Cadence in a 500, but the manual says it will work, with message waiting lamp).