I have just learned that evoca has a new feature - a skype call recorder. I know that it is possible to record skype calls using Audacity (some people report having difficulties recording both ends of the call) and powergramo, but recording a call with evoca was extremely simple.
All you have to do it create an evoca account and add evoca-skype-recorder as your skype contact. When you are in a call, you add the evoca contact to the call, and that's it! Your call recording will be stored in your evoca account. The first time you use it, you have to confirm your evoca account through a link sent to you through a skype message (it takes a few seconds).
Here is my first skype call recording, it's me and Nina Liakos:
The only pitfall is that you can only record up to 15 minutes for free. To record more than that you have to go pro in evoca and pay $29.95 a year.