For the past couple of days, I've been getting weird Baidu links via Skype chat. The sender is somebody I actually know and is my contact. The messages do not stay in the message history for that person, nor they never received the reply I sent back when the link was received. It's really weird to receive such links to a Chinese search engine in the first place, but the elusive chat history is the definite clue: somebody hacked Skype's protocol. Also, I find it strange, that the link contains my Skype-handle in it (obfuscated in below pic).
As the messages I got are from actual contacts, I followed up on them. Both persons deny sending me such links, and their message history doesn't display the link either. So, I don't think that the personal accounts are cracked, it's the Skype servers that are being exploited. Hopefully Microsoft-guys figure this out and plug the hole.
Couple hours after posting this, somebody posted a link to Why are Skype accounts getting hacked so easily? into Skype's community discussion. The article makes a claim that Skype's 2-factor authentication can be circumvented easily by using the old Skype credentials. Looks like you can still log in with Microsoft-account (pretty secure) or the credentials used before Microsoft acquired Skype. The old credentials cannot have 2-FA set up into it and most likely you already forgot it even exists. That seems to be the way how nasty people make their way in.
Update 10th Nov 2016:
Recent buzz is about a similar incident last year, when users' Skype accounts were used to send spam. So, nobody has come forward with any proof that the protocol would be compromised. It is gearing towards to the fact that users didn't realize there are two separate passwords to their Skype account, and the non Microsoft-account had a weak password which was used to gain access to contact lists.
Update 14th Nov 2016:
Confirmed, that this is not a case of using leaked passwords, my second post about this is here.