Call them using a Nokia. With my old 6310i you just tap the left 'soft button' twice and it will record your conversation. The person at the other end would hear a beep every few seconds, but you could always tell them your battery was going flat or something!
This should work on any Nokia with a voice recorder in 'Extras' I guess. The quality is perfect of course, but you don't have much memory on that old phone. New generation ones probably have more recording time.
Best thing is you can just pull the recordings off the phone with Bluetooth as .wav files.
If you have a Treo, it seems there is a
whole load of software out there that lets you do this too.