Recording a phone conversation is an FCC "NO NO" without a tap warrant, so don't expect to ever see a 2 way phone conversation recorder come OEM. I had a recording feature on another phone I had, but it would only record my half of the conversation. It was basically good if you ever had to remember what you told someone.
This is not correct. Recording a call to which you are a party is not generally considered a "tap" (i.e., surreptitiously recording both sides of someone else's conversation).
Federal law states that only one party must consent to the recording. This person may be the person recording the call (i.e., you don't have to tell the other person you are recording the call).
Many states have laws that follow the federal law (one party consent).
Gray areas are when a call is placed between states that have different state laws (i.e., recording a call placed in NY, where it is perfectly legal to record both sides of a conversation that you are a party to, to Massachusetts where all parties must give consent).
Windows Mobile phones come standard with a "Notes" button while on a call that allows you to record both sides of the conversation. It even documents the recording with the time and duration of the call.
I had an app on my old TREO that also allowed you to tap the conversation or if you were driving you just recorded someone giving you directions and then you replayed it as you drove along -- was a great app.
Are so-called 2-way phone recording apps really unavailable for the iPhone? What about the CallRec.Me and COGI recording services? Apple is certainly making these specific subscriber-fee based call recorders available at the AppStore. I'm not convinced that Apple is overly concerned with state laws regarding privacy so much as the survival and thriving of specific companies that require a user to register with a subscription plan in order to record phone and other recordable sources. Allowing standalone versions of such utilities would seriously hurt the bottom-lines of such companies ... if not jeapordize their outright existence. Forcing users' private recordings to be captured on the servers of outside third-party private companies hardly seems like going in the direction of protecting privacy rights ... it's in fact taking an opposite direction. So the argument for not having standalone call recording apps available for the iPhone due privacy issues (ergo via Apple and its AppStore) is dubious at best.
In the end, I hope that with enough expressed interest from the user-community as well as condemnation of "anti-competitive" services like CallRec.Me and COGI, there will be an opening up of the iPhone app world to "standalone" (ie: no requirement for outside subscription plans) call-recording utilities. There are some great ones out there (and have been for some time) like CallRec (by Andrej Molotov - for Palm Treos) ... Barring that, I'll have to seriously consider moving away from the iPhone and acquiring / using something more permissive and less intrusive.
Apple: The brighter the light ... the darker the shadow !