I did it with my VX4400 and audiovox 9500 by connecting the headset jack to the 3.5mm microphone jack on my computer and recording the message.
Just get a stereo 2.5mm male phono to 3.5mm female converter at radioshack and use a 3.5mm to 3.5mm cable to hook it up to your PC. It works like a headset without a mic.
When I did it, I used a 2.5mm male jack and wired it up myself, so you may have to reverse the polarity in order to get it to work.
---
Another way to do this is if your computer's modem has voice phone capability (many do). You can call up voicemail through your computer and record off the modem sound output.