Beside, these auto added contacts also have a different icon from the rest the actual Skype contacts. These contacts use icon which resembles an “Address Book” , unlike the normal Skype “Online” or “Offline” icons. And you cannot find “Remove from Contacts” option on right click context menu too to delete these contacts.
These “come from nowhere” automatically added contacts in Skype contact list is actually Microsoft Outlook contacts. If you have items or persons in Office Outlook (all versions applicable – Outlook 2000, Outlook XP, Outlook 2003, Outlook 2007, Outlook 2010, Outlook 2013, Outlook 2016 or newer included), these contacts will be added and shown directly in Skype contact list.
To remove these Outlook contacts, simply click on View or Contacts (for newer versions of Skype) on menu bar, then unselect (untick) Show Outlook Contacts option in the drop down menu.