If you have sprint, do the free Google Voice integration. Wonderful set of tools at your disposal afterwards.
You can listen to someone leaving you a voice-mail in real time, and even "beep" in for a lack of a better term.
Call recording is a push of a button during the call, and everything is saved online, voice-mail/text messages.
It's the bee's knee's.