Have you tried allowing auto registration? There is probably some parameter configured incorrectly. If you don't want to turn on auto registration, you can collect a packet capture from the phone and CCM traces to see what is going on.
There is also the off chance that it is a bad phone, try swapping in another phone of the same model and firmware version in the same switch port, if that one works fine and the broken phone stays broken on a 'known good' switchport, then open a TAC Service Request to see if the phone needs an RMA.
I'm not able to access my old voice mail messages all of a sudden. The recording says something like 'the message is currently not available'. This has never happened before in all the years I have been using this system. I have t...