That's odd, cause when you do a fresh restore, not at all from a back-up, all your VMs are there ready to be listened to.
The phone may store a local copy, but the server definitely stores a copy.
That's why I said copy. You can still call your voicemail to access messages. It was never a question of weather a copy is on the phone, server or in this case both, it was if they where stored in backups.