No jailbreaking or re-recording required!
This does require some familiarity with the command prompt (aka. command shell).
I was thinking of writing a small program or script to automate this but I am not sure what language to write it in.
I also don't really know how to illustrate this.
Step 1: When you sync your iPhone, iTunes backs up your files
Mac: ~/Library/Application Support/MobileSync/Backup/
Windows XP: \Documents and Settings\(username)\Application Data\Apple Computer\MobileSync\Backup\
Windows Vista and Windows 7: \Users\(username)\AppData\Roaming\Apple Computer\MobileSync\Backup\
Apple has some more information about iPhone and iTouch backups here.
It doesn't mention voicemail, but voicemail files are indeed included.