To find any person you previously chatted with on skype, all you have to do is open the skype main box... and at the top, click on VIEW and then click on INSTANT MESSAGES... and a list of every single person you ever chatted with will be listed. From there, all you have to do is right click on that name and select ADD TO CONTACTS... This is useful for finding/reading conversations you had with people weeks or months ago you were never on your contact list.
I never tried it personally, but if you've got your contacts in a file on your pc you can restore it from "Contacts" "Advanced" "Restore contacts from file". If you blocked someone you can unblock it by choosing "Manage Blocked Contacts". I didn't find more options about "undeleting" a Skype contact, but I hope you'll find the solution.