Is an iPhone call recorder theoretically possible?
On Jailbroken iPhones, SpoofApp does call recording. I am not a laywer, but note that recording calls may not be legal depending on where you are and/or where the other party is.