EvilZone

I highly doubt that websites like that are legit (it reminds me website offering Facebook hacking services "Enter victims username and send us payment" bullshit). At first you can simply delete your part of conversation it will make hard for other person to remember or any 1 else to know what you were talking about. And the part where you want to remove his part of conversation is more complicated. If it's very necessary for you to do it you can try Rat'ing his computer and delete history when he is afk (it's up to you). Keyloging won't help because Skype doesn't remember history on other computer only on one that conversations happened.(Can't remember for 100% because haven't used Skype in ages).
Oh, and lately saw services on underground forum offering Skype banning for $20 or something like that. You could search for it.
Don't want to advertise that forum or those services :p