What you said was largely what I was talking about, except this line.
mp3, not wav. Lets go with the generic and more widely usable format.
But, yes, I'd love it if all of my voicemail sources could be told "email my voice mail to me as MP3 files". Preferably with the sending phone number and caller-id in the subject line, like:
From: AT&T Voice Mail <some@where.tld>
To: Me <home@email.tld>
Date: (whatever)
Subject: +1-408-555-1234 Private Caller
Where I know that "AT&T Voice Mail" means my home voice mail. For work, it'd be "(My employer's name) Voice Mail" or something. For my cell, it'd be something like "T-Mobile Voice Mail".
If all of my phone sources did that, And my G1 could play those MP3's right out of my gmail account, that would be ideal.