Cell phone with good "call-recording" function

[Guest salad_tosser]

I am looking to buy an new phone. One of the features that is important to me is being able to record my phone calls (both incoming and outgoing).

I already have cool hardware to do that (http://www.qvcvideo.com/main/products/?category=26&bcat=14), but I want the ability to do it already built-in to my phone.

Could you please suggest non-clunky phones that give call-recording functionality, perhaps with a one-touch button for call-record and lots of storage (or storage potential)? Smart phones with this functionality would be very welcome.

Thank you,

Poppy