It's likely pointing to the HCI route on the resilient controller.
Try this:
Leave a test voicemail on one of the affected phones.
With that phone on-hook, press the voicemail key.
Press Read Message. At the very top of the screen, it should show "Call <number of your HCI route>" If it shows a different number then this will explain why you get the "invalid" message.
Press "Erase Msg". This will delete the test voicemail.
Do these same steps again. You should get the valide HCI route at this point.