How can I convert iPhone .m4a recordings to a more common and lossless format? what's the best way to convert .m4a to a more common song format, like mp3 etc.

The m4a files are recorded by the iPhone and my machine runs windows vista home premium 32-bit sp2

I want it to be as lossless as possible. (hopefully possibly 0%)
If the song is already in iTunes, it's easy to do it right within it. Go to the iTunes Preferences and choose "Import Settings" on the "General" page. You can set the desired output format here. Afterwards, select the songs you would like to convert and choose Advanced > Create XY Version, where XY is the file format you specified in the Import Settings. When iTunes has finished converting the files, you will have each track twice - you could use a smart playlist to filter the ones in the new format.

Bear in mind that converting from one lossy format to another lossy format will always result in a lower quality.