Coolsmartphone France found this really cool utility which allows you to record your telephone calls on your Smartphone.

PMRecorder is available at : http://1800message.com/usepmr.aspx