I've been chasing this unicorn since my HTC WM6 titan. I've been using XJ MIUI for the Desire that has a built in automatic call recorder in the ROM. It works flawlessly and as been implemented for well over a year now. I have treads on several of the MIUI dev sites to adapt this ability to "on phone voicemail". No Dev's have bitten yet because of the false perception that no-one wants this capability.
A simple Google search can disprove that idea, the requests for such an app are all over the web. As far as I can tell MIUI roms are the easiest route because of the highly customized kernel that already allows applications access to the voice stream. It even has a setting where you can allow or block 3rd party applications access to the stream.
So here's what i'd like to suggest. If your a flasher who likes trying new roms for hoot, then swing over to XDA and try out XJ's MIUI Rom if you have a Desire (ver. X-Part on desire clocked to 1.2 is very impressive). There are others porting MIUI to various devices all over XDA. If you like the Rom post to the tread and ask for this capability to be included. If enough requests are heard then some Dev will look at it and fix it up. Once one starts working on it more always follow. Because of the distro method for MIUI if one gets it working it will spread like wildfire to more devices.
Its worth a try. There will never be a voice mail recorder app in the market. Carriers don't want phones that can record voice mail, its a revenue source tho they say its a legal issue. So Google doesn't want them upset and therefore the code to do this is removed from the source.
It still blows my mind that crap like talking tom cat is on the top of the software lists while real life useful functionality like this idea doesn't exist.
I'd post the links to all of this stuff but I'm not allowed yet. No matter, a search will get you everything.