Until the API is opened enough to provide true conversation recording, Google Voice actually works pretty well for this purpose, if you have a GV number forwarded to your Pre. I've used it a few times to record interviews that I need to transcribe and the sound quality of the call recipient is perfect; your voice, on the other hand, is only recorded as well as how it sounds coming into the mic. But the other end is recorded straight from the "line source."
Anyway, you obviously have to have a Google Voice account to use this feature. Also, call recording in GV is currently supported for incoming calls only, however there's an easy work-around to record outbound calls... Here are the instructions, taken from the official Google Voice help forums (a user submitted this solution, along with an explanation of why GV hasn't adopted outbound call recording yet):
Once you create that "Call Widget" you can just copy a shortcut to it on your desktop or in your Web browser and use it whenever you need to record an outbound call.
If they enabled recording outgoing calls it could cause problems when you dialed automated lines and had to key in numbers. Like calling the bank. It's not a pretty way to do things but if you want to record an outgoing call you need to initiate it using a Call Widget.
Call Widgets can be put on any web page, and allow people to call from that web page. When somebody clicks on the widget, we call them and connect them to you. Your number is always kept private. You can create multiple call widgets and have different settings for each of them.
Note: The GV recording feature plays a short announcement to both parties that the call is being recorded. I think I remember reading that there is also a work-around or trick to disable it, but I can't remember where. But like I mentioned, for things like interviews it works great!