Does your cell phone offer the speaker phone option? That's where you don't have to hold it up to your ear to hear what the other person is saying.
In a "QUIET" location free of background and movement noise not placing a mic on a hard surface for example playing back the message with the phone next to the mic eliminates the need for trying any direct plugins to the phone. The messages would be recorded by the Windows sound recorder as wav files at first where you would then use any one of a large number of freeware wav to mp3 converter programs floating around the web to make the file conversions.
C/NET has a review on one
Wav to MP3 Converter to look over and give a try. This would be the type of converter to go with over simply finding them on unknown sites since this site is offering a review. That insures any downloads are free of any "unwanted" items like adbots, spybots, and be sure to uncheck any unwanted tool bar addons with any freewares as well when going to try any out.
Can't guaranty the sound quality by way of cell phone speaker to mic however. For that you would need to test the idea and adjust the input level as well as how you position both mic and phone for the best recording. The file conversion is the easiest part!