I find I usually keep some blank paper around or in a drawer of my desk for various uses, including general calculations, scrap work, rough outlining, notetaking, and also, for capturing the voicemails. From there, once I've got the notes from the calls out of the VM system, then I can decide what to do. As mentioned above, if its quick (2-minute rule) you can potentially take care of it right away and then the note can be tossed, or put into a contact file, or something along those lines. If its non actionable and you don't need it for reference, again, it can be tossed. And if its going to be longer, than based on the information you've copied out, you could potentially either copy it into your trusted system, whether that be paper or electronic based, as an action, as an agenda for the next meeting with that person, or however that works for you.
If your a hipster PDA user, and you make the notes right on index cards, then perhaps you just then file said card in the relevant location.
Hope this helps . . .