I'm not sure I completely understand the question. Users voicemail messages are stored in their Exchange inbox. If a pervious user had old voicemail messages and you have re-assigned that extension to someone else, the point of focus should still be on deleting the email messages out of the old Exchange inbox for the user no longer at that extension.
If this is not the case, can you please explain your situation more carefully and also explain what you "restored" as well as how you know there are email messages you cannot access.
Will
----------------
Will Roach
Systems Engineer
Cisco Systems, Seattle - TAC