The most important thing that you have to keep in mind about "free" online services is that you are not their customer. You are the product that they're selling. Their real customers are the advertisers and government entities that are paying them for the analytics data they've collected on you. Google, Microsoft, Facebook, Twitter, Yahoo!, etc. are information brokers in that regard, and the tactics they use to gather this information are as shrewd as they are sophisticated.
I can't say specifically how Skype knows who "Alex" is, but you can bet that it inferred the relationship based on common browser fingerprinting techniques.
Here's a simplified example of how this works:
Let's say you visit the web page of a local bike shop that has a Facebook "share us" or "like us" button on it. Congratulations, you are now the proud owner of a Facebook cookie. That cookie contains an ID number that is tied to specific information that can be easily gleaned from the page hit; your IP address, browser name and version, installed fonts, installed plug-ins and their versions, operating system, language, etc. The combination of all these metrics can identify you uniquely out of the millions of other computer users out there.
Now that they've got the fingerprint, they build a dossier on you, attached to that fingerprint. Every site you visit with those Facebook buttons on it can read that ID and sends this information back to Facebook. As you travel around the Internet, Facebook tracks you and knows what sites you've visited and when. If you landed there from a Google search, they know what your search query was too. Over time this data paints a picture of who you are; your tastes, interests, habits, hobbies, political leanings, etc. This data is aggregated and cross-referenced with other users to create association maps -- other people you know, how and when you interact with them, how close you are, and most importantly, how your interests and tastes relate to theirs.
This is literally billions of dollars' worth of information they're collecting on you. And they have a vested interest in getting you to strengthen these association maps; being "helpful" by suggesting things their algorithms say you might be receptive to -- such as coupons from vendors you've done business with, or friending other people you may know. The kicker here is that you don't even have to be a Facebook user for this system to work.
Now, all of the major players on the Internet do this. Many of them are companies you've never even heard of, such as DoubleClick, Akamai, Taboola, WebTrents, and so on. I call Facebook out here in my example because A) they're not shy about what they're doing, and B) their entire business model is based on it, unlike Microsoft and Google who actually have other products to sell.
Skype is owned by Microsoft. YouTube is owned by Google. Instagram is owned by Facebook. every time you use pretty much any online service, you cross-contaminate with other services you've used. Google knows who your Facebook friends are. Microsoft knows who your Gmail contacts are, and Facebook knows who your Hotmail contacts are. And all of them know more about you than your own mother does.
Skype doesn't interact with Google Mail at all. – Ramhound – 2017-01-31T05:22:47.793
More likely that Skype got the contact data from an Outlook account - on computer or from online store of address book/contacts. MS bought Skype in 2011 and has pursued integration to compete with Hangouts. – user686699 – 2017-01-31T05:29:14.300
@GypsySpellweaver I don't maintain contacts in Outlook/Hotmail at all and one of the new potential Skype contacts is somebody I recently added to Gmail and Gmail only. I don't know what you mean by "Outlook account - on computer". I've never seen such a thing because I only use Gmail and Outlook/Hotmail via browser. – H2ONaCl – 2017-01-31T05:37:23.130
I can't see down votes, so I don't know. Don't see any reason for it either. If you don't use outlook locally, then it don't matter. But, you do use Hotmail online.. Do you have any mail to/from the one you added to Gmail in your outlook email? And from the ones you do or don't recognize from the last two groups in the question? – user686699 – 2017-01-31T05:47:17.173
Just assumption... May be it comes from the same feature as WiFi sense (that share Wi-Fi network access with your Facebook, Outlook.com, and Skype contacts), as process of more deep integration with social trap net ... – Alex – 2017-01-31T06:30:04.630
Something sounds fishy there. No other clues how it got there. Part of the reason I don't trust MS - too much back-door activity for my tastes, and trust. I dropped Skype when Redmond acquired it. Hope you find the hole, and plug it. – user686699 – 2017-01-31T06:56:36.953
What E-Mail address is "Alex" using? It it a Microsoft address? He might just have you as a contact. In addition, depending on what other data is available from other contacts, it might be similar to how e.g. Facebook suggests you new persons. – Seth – 2017-01-31T08:47:30.953
Are you perhaps using Skype on any device where your GMail contacts appear in the “global” address book? Like a phone or whatever. – Daniel B – 2017-01-31T08:49:03.107
@Seth, Alex M**** is on Gmail. I have emailed Alex to ask if he has any insight into this problem. – H2ONaCl – 2017-01-31T08:58:52.447
@DanielB, I used to use Skype on an Android phone up until about a few weeks ago and then I stopped and did a factory reset because I was worried about privacy. The phone was installing apps without my permission even after a factory reset. Although I used Skype on the phone I never used Skype to contact Alex M****** on the phone. I don't know anything about the phone's address book. Perhaps his phone number was in there for a few days or weeks. – H2ONaCl – 2017-01-31T09:03:26.840
What do you mean it was installing apps without your permission? If Skype was on that phone and had the permission to read your address book it's likely what happened. – Seth – 2017-01-31T11:10:46.157
@Seth apps would appear that I could not locate in the Play Store. I turned off the phone after a factory reset and I have not used it in weeks. The new potential contacts in Skype appeared today. However I agree that it looks like it could be the cause but it's not plausible that Microsoft would install malware on Android in order to get me to have more Skype contacts. – H2ONaCl – 2017-01-31T11:48:59.750
But if you installed Skype on that Android phone it would not be malware because you installed it? In addition there are usually apps that are only available from whatever vendor you got that won't appear in the store. If they actually appeared some time after you did the reset you might indeed be facing something strange. – Seth – 2017-01-31T11:53:34.600