Total Recall: Caused stability issues on my phone - switching away from the active call window would often cause the windowshade to not work correctly, making it hard to return to the call. General odd behavior.
Call Recorder (Schass Innab): Worked, but the incoming voices was much quieter than the outgoing voice. Widget was nice, but too quiet.
AllCallRecorder: Works. Incoming is still quieter than outgoing, but not as bad as Call Recorder (I think). No widget, but seems stable.
[Edit]: To alleviate the low volume on the incoming voice, turn the call volume on the phone up all the way. It will not fix the problem completely, but it will help a bit.
[Edit 2]: The incoming call volume appears to vary call-to-call. I was on the phone with a fellow and got cut off, so he called me back. The first call, when I called him, had somewhat low incoming call volume. The second call, when he called me, had quite loud incoming call volume. I don't know why, as no settings were changed. Perhaps the system works better when people call you, rather than when you call them?